\documentstyle[proc,12pt]{article}
\newcommand{\dino}{{\shrink DINO}}
\newcommand{\dinoB}{{\shrink \bf DINO}}
\newcommand{\envexp}{{\shrink ENV\_EXP}}
\newcommand{\ebnf}{{\shrink EBNF}}
\newcommand{\ebnfB}{{\shrink \bf EBNF}}

\newcommand{\sectionX}[1]{\vspace{-12pt}\section{#1}}
\newcommand{\subsectionX}[1]{\vspace{-12pt}\subsection{#1}}
\newcommand{\subsubsectionX}[1]{\vspace{-12pt}\subsubsection{#1}}

\newcommand{\itemX}[1]{\vspace{12pt}\item #1\vspace{6pt}\parindent 2em}
\newcommand{\itemXfirst}[1]{\item #1\vspace{6pt}\parindent 2em}
\newcommand{\itemXblank}{\vspace{12pt}\item[]\vspace{6pt}\parindent 2em}

\newcommand{\itemY}[1]{\item[\tt #1\quad]}
\newcommand{\itemZ}[1]{\item[\underline{#1}]}

\newcommand{\spacer}{\vrule height8.0pt depth3.0pt width0pt}
\newcommand{\boxX}[1]{{\fboxsep 2pt\fbox{\em \spacer#1}}\kern+1pt}
\newcommand{\boxY}[1]{\verb|<|{\em #1}\verb|>|}

\newcommand{\path}{\boxY{path}}
\newcommand{\filename}{\boxX{filename}}
\newcommand{\env}{\boxX{env}}
\newcommand{\mach}{\boxX{mach}}

\newcommand{\bold}[1]{{\bf#1}}
\newenvironment{itemizeX}{\begin{itemize}\vspace{-8pt}}{\vspace{-8pt}\end{itemize}}

\newenvironment{quoteX}{\list{}{\listparindent 0em
 \itemindent\listparindent
 \leftmargin 0em \rightmargin 0pt \parsep 0pt plus 1pt}\item[]}{\endlist}

\newenvironment{quoteXX}{\list{}{\listparindent 0em
 \itemindent\listparindent \topsep 0pt \partopsep 0pt
 \itemsep 0pt
 \leftmargin 1em \rightmargin 0em \parsep 0pt}\item[]}{\endlist}

\def\leaderfill{\leaders\hbox to 1em{\hss.\hss}\hfill}
\newenvironment{entry}[1]{\begin{quoteXX}#1}{\end{quoteXX}}

\newcommand{\entryX}[1]{\begin{quoteXX}#1\end{quoteXX}}

% The following commands are designed to set up to produce an index

\openout15=\jobname.index
\newcommand{\out}[1]{\write15{#1}}
\def\idx{\string\idx}
\def\ixs{\string\quad}
\def\ix{\string~}
\def\ppar{\string\par}

\newcommand{\indexA}[1]{\out{\idx{\ix#1\ix\ix\ix0\ix}{\ppar\space#1}}\out{\idx{\ix#1\ix\ix\ix\thepage\ix}{,\ix\thepage}}}

\newcommand{\indexB}[2]{\out{\idx{\ix#1\ix\ix\ix0\ix}{\ppar\space#1}}\out{\idx{\ix#1\ix#2\ix\ix0\ix}{\ppar\ixs\space#2}}\out{\idx{\ix#1\ix#2\ix\ix\thepage\ix}{,\ix\thepage}}}

\newcommand{\indexC}[3]{\out{\idx{\ix#1\ix\ix\ix0\ix}{\ppar\space#1}}\out{\idx{\ix#1\ix#2\ix\ix0\ix}{\ppar\ixs\space#2}}\out{\idx{\ix#1\ix#2\ix#3\ix0\ix}{\ppar\ixs\ixs\space#3}}\out{\idx{\ix#1\ix#2\ix#3\ix\thepage\ix}{,\ix\thepage}}}

\begin{document}

% The following definitions, etc., set up the listing function, which is
% designed to import an external file in verbatim fashion.

\def\uncatcodespecials{\def\do##1{\catcode`##1=12 }\dospecials}
\def\setupverbatim{\tt
		   \def\par{\leavemode\endgraf\mbox{}} \catcode`\`=\active
		   \obeylines \uncatcodespecials \obeyspaces}
\def\listing#1{{\parskip 0pt \parindent 0pt \begingroup\setupverbatim\input#1 \endgroup}}
{\catcode`\`=\active \gdef`{\relax\lq}}

\newcommand{\doex}[2]{{\vspace{0.375in} \noindent \bold{Example #1: #2} \par \vspace{0.375in} \hsize = 7in \small \listing{../#2} \newpage}}

\tableofcontents

\newpage

\sectionX{Introduction}

\dino\indexA{DINO} (DIstributed Numerically Oriented language)
is a language for writing parallel programs
for distributed memory ({\small MIMD})\indexA{MIMD} multiprocessors.
It is oriented towards expressing data parallel algorithms,
which predominate in parallel numerical computation.
Its goal is to make programming such
algorithms natural and easy, without hindering their 
run-time efficiency.
\dino\ consists of C\indexA{C} augmented by several high level
parallel constructs that are intended to allow the parallel program to
conform to the way an algorithm
designer naturally thinks about parallel algorithms.
The key constructs are the ability to declare a virtual
parallel computer\indexA{virtual processors}
that is best suited to the parallel computation,
the ability to map distributed data
structures\indexA{distributed data structures} onto this virtual machine,
and the ability to define procedures that will run on each
processor of the virtual machine concurrently.
Most of the remaining details of distributed parallel computation,
including process management and interprocessor communication,
result implicitly from these high level constructs and are
handled automatically by the compiler.

Section~\ref{basic dino} contains a short description of the \dino\ language,
followed by a methodology for writing \dino\ programs, and two examples.
The definitions of all \dino\ constructs are in
Section~\ref{language reference}.
Section~\ref{examples} has a number of examples, with a features index.
Section~\ref{using dino} contains information about how to setup \dino\,
and how to use the compiler itself.
Section~\ref{hints} contains a list of known compiler bugs,
plus hints on run-time errors and performance.
Information on how to install \dino\ is contained in
Section~\ref{installation}.
Finally, Appendix~\ref{ebnf} contains a complete \ebnf\ specification
for the \dino\ extensions to the C language.

\vspace{0.5in}
{\Large
This manual is probably unlike any manual you have used before.  In particular,
Section~\ref{basic dino} gives a conceptual overview of how a programmer should
approach writting \dino\ programs, along with two examples of how to use this
approach.  Section~\ref{examples} gives a large number of example programs
that illustrate various \dino\ features.
We suggest that new users should probably read Sections~\ref{basic dino} and
\ref{using dino}
in order to get started.  Users can then proceed to the examples in
Section~\ref{examples}, or read the reference material in
Section~\ref{language reference}.
}
\vspace{0.5in}

\sectionX{Basic \protect\dinoB}
\label{basic dino}
\subsectionX{What \protect\dinoB\ Is}

\dino\indexA{DINO} is a language for writing
parallel numerical programs for distributed memory multiprocessors.  
By a distributed 
memory multiprocessor we mean a computer with multiple, independent processors,
each with its own memory, but with no shared memory or shared address space,
so that communication between processors is accomplished by
passing messages.  
Examples include {\small MIMD} hypercubes, and networks of computers used
as multiprocessors.

It is generally harder to design an algorithm 
for a multiprocessor
than for a serial machine, because
the algorithm designer has more tasks to accomplish.  
First, the algorithm designer must divide the desired computation
among the available processors.  
Second, the algorithm designer must decide how these
processes will synchronize. 
In addition, on a distributed memory multiprocessor,
the algorithm designer must consider how data should
be distributed among the processors, and how the processors
should communicate any shared information. 

The goal of \dino\ is to make programming
distributed memory parallel numerical algorithms as easy as possible,
without hindering efficiency.
We believe that the key to this goal is raising the task of
specifying algorithm and data decomposition, 
interprocess communication, and process
management to a higher level of abstraction than is
provided in many current message passing systems.
\dino\ accomplishes this by providing high level parallel constructs
that conform to the way the algorithm designer
naturally thinks about the parallel algorithm.  
This, in turn, transfers many of the low-level
details associated with distributed  
parallel computation to the compiler.
In particular, details regarding message passing, 
process management, and synchronization 
are no longer necessary in the code that
the programmer writes,
and associated efficiency considerations are addressed by the compiler.

This high level approach to distributed numerical computation is feasible 
because so many numerical algorithms are highly structured.  
The major data structures in these algorithms are usually  arrays.  
In addition, the algorithms usually exhibit data parallelism, 
where at each stage of the computation,
parallelism is achieved by dividing the data structures into pieces, and 
performing similar or identical computations on each piece concurrently.
\dino\ is mainly intended to support such 
data parallel\indexA{data parallelism} computation, although  
\dino\ also provides some support for functional
parallelism\indexA{functional parallelism}.

The basic approach taken in \dino\ is
to provide a top down description of the distributed parallel algorithm. 
The programmer first defines a virtual parallel\indexA{virtual processors}
machine that best fits the major data structures 
and communication patterns of the algorithm.
Next, the programmer specifies the way that these
major data structures will be distributed,
and possibly replicated, among the virtual processors.  
Finally, the programmer provides procedures that will
run on each virtual processor concurrently. 
Thus the basic model of parallelism is
Single Program Multiple Data\index{SPMD (single program, multiple data)},
although far more complexity is possible. 
Most of the remaining details of parallel computation and communication are
handled implicitly by the compiler.
A key component in making this approach viable has been the
development of a rich mechanism for specifying
the mappings\indexA{mapping functions} of data structures to virtual machines,
along with the efficient implementation of these mappings
and the resultant communication patterns in the compiler.  

Sequential code in a \dino\ program is written in standard C\indexA{C};
\dino\ is a superset of C.
Only the parallel constructs in \dino,
and a few related additions, are new.

\subsectionX{Basic Programming Model}

Rather than just jumping in and confusing yourself with all the syntax of
\dino, we believe it is more useful to start by looking at a conceptual
overview of how \dino\ programs are written.  We have followed this by
two examples which show how to proceed from algorithm to finished code.
The first of these examples is extremely simple, the second more complex.

We urge you to read the overview section, and at least the first example.
This should give you enough of the flavor of \dino\ that you will understand
the formal language definition and examples (in
Sections~\ref{language reference} and~\ref{examples}).

\subsubsectionX{\protect\dinoB\ Overview}\indexA{Overview of DINO}

When writing programs in \dino, we have found it useful
to proceed in a specific sequence of conceptual ``steps.''
Our particular way of looking at the process of solving a problem in \dino\
helps us to structure the solution so it best fits the \dino\ paradigm.
We suggest that you try this method of organizing the process of turning
your solutions into \dino\ code at least long enough to get an idea of how
we feel you should think about parallel numerical problems in \dino.
There are five specific ``steps'':

\begin{itemizeX}

\itemX {Step 0 --- Begin with a good understanding of
the problem and a general approach to its solution.}

In order to use our method, you must begin with a good understanding of
your problem and a general approach to its solution, including what
you believe the main data structures should look like and an idea of
how work can be divided among a number of processors.

\itemX {Step 1 --- Choose a \underline{\em structure of environments}
appropriate to the problem.}\indexB{Overview of DINO}{structure of environments}

In \dino, environments are virtual processors\indexA{virtual processors}.
In the current version of \dino,
there should be only one virtual processor for each real processor on the
target machine, due to memory and speed limitations.
A group of environments that is used for a particular computational
task is structured (a vector, 2D array, etc.) to make it easier
to visualize how the data and the work is divided up and to make it
easier to name particular environments.

You choose the particular structure of environments by having some
idea of how your data structures will be broken up.  If, for example,
your major data structure is a 2D matrix and you want to send each
row to an environment, choose a vector of environments.  If your
major data structure is a 2D matrix and you want to send each
element to an environment, choose a 2D array of environments.
Obviously, if you have more than one data structure, the
environment structure must be the same for each or you need to
clarify how your solution will work.

\itemX {Step 2 --- Determine how the principal data structures should be
distributed among the environments in the structure you have chosen
(specify the \underline{\em mappings}).}\indexB{Overview of DINO}{mappings}

For each of your data structures, you should specify how it is
mapped\indexA{mapping functions}
onto the structure of environments you have decided to use.
Conceptually, this task can be divided into three parts:

	\begin{itemizeX}

	\itemX {Determine the basic \underline{\em partitioning}.}
\indexA{partitioning of data structures}

	Most of your major data structures will be broken up and distributed
	among the environments in the structure of environments that you
	specified.  For example, if you have an $N$ by $N$
	array named $A$ to be distributed to a structure of environments
	named ``node'' which is a vector of size $N$ you might want to think
	of putting one row on each environment so that $A[0][]$ is on node[0].
	It is useful to think of node[0] as the owner of $A[0][]$ or of
	node[0] as being the home of $A[0][]$.

	\itemX {Determine any \underline{\em replication}.}
\indexA{replication of data structures}

	In some cases, you will want to have the same data structure copied
	(replicated) on all environments in a structure of environments.
	You will want to do these when every environment needs access to the
	same values.
	While you can think of this as ``partitioning'' the data structure
	so that the whole thing goes to the first environment, then placing
	complete ``copies''\indexB{copy data}{as opposed to replication}
	on all the other environments (see the next
	point), it is confusing to view it this way (this is how it is
	actually implemented).  Instead, think of these data structures as
	simply replicated everywhere.

	\itemX {Determine where any \underline{\em copies}
	(used for communication) go.}
\indexA{copies in distributed data structures}

	Finally, you may want to determine that copies of parts of the data
	structure
	should be on environments other than the ``home''
	environment\indexA{home environment} for that part
	of your data structure.
	These copies will be used to indicate that you will communicate
	values for this data from the "home" environments to the
	environments where the copies are.
	The environments in which this copied data is
	placed are referred to as ``copy''
	environments.\indexB{distributed data}{copy environment}
	For example, if you have broken a 2D array
	up by columns, each environment might need the values from the
	neighboring columns to do its computations.  In this case, you would
	want a copy of each column to be on the environments to the ``right''
	and the ``left'' of the ``home'' environment for that column (except
	for the end columns).

	The compiler uses this copy information to simplify communications.
	When you tell \dino\ to ``send''\indexA{sends} the ``home'' column,
	it knows to send
	it to the environments where copies exist.  When you tell \dino\ to
	``receive''\indexA{receives} a ``copy'' column, it knows what
	environment to receive
	it from.  (The compiler also creates permanent storage for any ``copy''
	data on an environment, a fact you may find important if you have very
	large data structures.)

	\end{itemizeX}
\noindent
The mechanics of specifying this to \dino\ are usually simple.  There are a
fair number of predefined mappings\indexB{mapping functions}{predefined}
in the include file
``dino.h''.\indexA{dino.h (include file for predefined mappings)}
For example, \bold{Block}
puts each element of a vector on an environment in a vector of environments
(assuming the number of elements equals the number of environments).
The mapping function \bold{all} replicates a data structure on each environment.
\bold{BlockOverlap}
puts each element of a vector on an environment in a vector of environments
and a copy of each element on the two neighboring environments (except for
the edges).  You simply use the one of these that fits your situation.
If you have to, you can build your own
mappings\indexB{mapping functions}{user defined} (information on this
process can be found in Section~\ref{mapping definition}).
	
\itemX {Step 3 --- Write a \underline{\em composite procedure} to implement
computation in the structure of environments.}
\indexB{Overview of DINO}{composite procedures}

Determine what computations will take place in an environment.  The
code should be written for one environment.  This means that you must have
some way of identifying the particular environment your code is executing
on.  That is the function of the identifiers in the declarations for each
of the environment indices, referred to in this manual as
{\em environment index identifiers}.\indexA{environment index identifiers}
For example, if the environment declaration is
``{\tt environment node[10:id] \{ $\cdots$ \}}'',
``id'' is a constant that contains
the number of the current environment.

You can conceptually break writing a composite procedure down into three
``steps'':

	\begin{itemizeX}

	\itemX {Write the code for the \underline{\em computation}.}

	Write the code for one environment assuming that all the
	necessary data is available there.

	\itemX {Insert any necessary \underline{\em receives}.}
	\indexB{overview of DINO}{receives}

	If during the computation, you will need updated values in
	the data that is ``copy'' data\indexA{copy data} on this environment,
	put in receives
	for that data.  A good rule of thumb is to put the receives in as
	late in the computation as possible.
	A second rule of thumb is that data communicated between environments
	should be sent and received in as large blocks as is possible.
	Obviously, these two rules sometimes conflict, and you must decided
	what the best trade-off is.

	\itemX {Insert the corresponding \underline{\em sends}.}
	\indexB{overview of DINO}{sends}

	Finally, you have to put in sends corresponding to the receives you
	inserted in the last step.  Again, a good rule of thumb is to put
	the sends in as early in the computation as possible, and to send
	in blocks where possible.

	\end{itemizeX}

\noindent
When doing these steps, we've found that it's best to write code for the
``middle'' first.  Most of the complications in \dino code occur at the
``edges,'' so we suggest that you write code for the middle first.  Then
modify it to take into account the extra complications introduced by the
edge conditions.

We mean ``middle'' in two senses --- spatially and temporally.
Spatially means the middle of your distributed data structures.  Often,
more complicated code has to be written for the edges, for one of the
following reasons:

\begin{enumerate}

\item The actual edge of the global data structure may have different
communication patterns than the central portions.  Your code may need to
reflect this.

\item If you block your distributed data (put more than one element on an
axis in an environment,) then then edge of the block on an environment
may have to be treated differently.

\end {enumerate}

Temporally means that the first and last iterations of a loop are often
different than the others.  For example, \dino\ initializes copy data when
parameters are distributed.  This may mean that a first send/receive pair
is unnecessary.

\itemX {Step 4 --- Finally, write a
\underline{\em host environment},\indexB{overview of DINO}{host environment}
containing a
\underline{\em main() function},\indexB{overview of DINO}{main() function}
to implement computation on the host environment.}

Write the code that does any initialization, calls the composite
procedure(s), and processes the results from the composite procedure(s).
All the data used by composite procedures is passed in as parameters to
these procedures.  \dino\ will automatically distribute this data in the
manner specified by your mappings.

\end{itemizeX}

\subsubsectionX{Walkthrough}
\indexA{walkthrough}
\indexB{overview of DINO}{walkthrough}

To illustrate writing a \dino\ program, we offer two examples.
The first is a very simple program intended to show the basic application
of the principles outlined in the overview.  The second is a
somewhat more complex example intended to show some of the subtleties
involved in using \dino.  We will walk through the steps outlined above
for each example to illustrate the process.

These examples illustrate the thought process that a programmer should go
through when writting a \dino\ program.  To get much out of them, they have
to be read carefully and not just skimmed.  We recommend setting aside
some time to work through them carefully.

\subsubsectionX{Matrix-Vector Multiply}
\indexC{examples}{matrix vector multiplication}{walkthrough}

This example takes  a very simple problem, a matrix-vector multiplication
where the number of rows in the matrix is the same as the number of
processors available, and shows how to write a \dino\ program to solve
this problem.

\begin{itemizeX}

\itemX {Step 0 --- Begin with a good understanding of the
problem and a general approach to its solution.}

The algorithm is almost trivial --- each element of the solution vector is
obtained by taking the dot product of the corresponding row of the
multiplicand matrix with the multiplicand vector.  To parallelize this
problem, we will choose to send each row of the multiplicand matrix to
a processor, a copy of the multiplicand vector to each processor, and
collect each element of the answer vector back from the processors.

If we draw a picture of our algorithm (we usually
resort to drawing pictures to understand all but the simplest algorithms),
we get something like this:

\end{itemizeX}

\begin{center}
\begin{tabular}{|l| l |l| l |l|} \cline{1-1} \cline{3-3} \cline{5-5}
 & & & & \\
 & & & & \\ \cline{1-1} \cline{5-5}
 & & & & \\
\hspace{1.25in} & & \hspace{.2in} & & \hspace{.2in} \\ \cline{1-1} \cline{5-5}
 & {\Large {\bf X}} & & {\Large {\bf =}} & \\
 & & & & \\ \cline{1-1} \cline{5-5}
 & & & & \\
 & & & & \\ \cline{1-1} \cline{3-3} \cline{5-5}
\end{tabular}
\end{center}

\begin{itemizeX}

\itemX {Step 1 --- Choose a \underline{\em structure of environments}
appropriate to the problem.}
\indexB{structure of environments}{in matrix vector multiplication}

Given the way we have decided to break up the problem, a vector of
environments seems appropriate.  We will use a structure
of environments the size of the machine (which we assume to be 16).  So our
code initially looks like this:

\begin{quotation}\begin{verbatim}
environment node[N]
   {
   }
\end{verbatim}\end{quotation}
\noindent
To make things easier to change, we will use a macro definition -- $N$,
which will represent both the size of the machine and the size of the array
and vectors (16).

\itemX {Step 2 --- Determine how the principal data structures should be
distributed among the environments in the structure you have chosen
(specify the \underline{\em mappings}.)}
\indexB{mapping functions}{in matrix vector multiplication}

	\begin{itemizeX}

	\itemX {Determine the basic \underline{\em partitioning}.}
\indexB{partitioning of data structures}{in matrix vector multiplication}

	Lets call the multiplicand matrix $A$,
	the multiplicand vector $B$, and the solution vector $C$.  We block $A$
	by rows and $C$ by elements.  (We don't partition $B$ at all; see the
	next point.)

	\itemX {Determine any \underline{\em replication}.}
\indexB{replication of data structures}{in matrix vector multiplication}

	We want a complete copy of $B$ on each environment, so we replicate it.

	\itemX {Determine where any \underline{\em copies}
	(used for communication) go.}
\indexB{copies in distributed data structures}{in matrix vector multiplication}

	There is no inter-processor communication in this program (except, of
	course, for parameter distribution and collection, but that is totally
	automatic.)  Thus, no copies are needed.

	\end{itemizeX}

The mappings that give the partitioning we want are
\bold{BlockRow}\indexB{mapping functions}{BlockRow},
\bold{all}\indexB{mapping functions}{all}, and
\bold{Block}\indexB{mapping functions}{Block}.
(We looked at the predefined
\dino\ mappings\indexB{mapping functions}{predefined} to find this ---
see Section~\ref{predefined mapping functions}.)
Our declarations therefore look like:

\begin{quotation}\noindent\begin{verbatim}
float distributed A[N][N] map BlockRow;
float distributed B[N] map all;
float distributed C[N] map Block;
\end{verbatim}\end{quotation}

\itemX {Step 3 --- Write a \underline{\em composite procedure}
to implement computation in the structure of environments.}
\indexB{composite procedures}{in matrix vector multiplication}

	\begin{itemizeX}

	\itemX {Write the code for the \underline{\em computation}.}

	This is almost trivial.  We need a single loop to do the dot product.
	The only complication is that we must know which environment we are on
	in order to know which row of $A$ and element of $C$ to use in the
	computation.  There is a special constant we can declare that will have
	the value of our index in it, which is known as an
	\underline{environment index identifier}
	\indexA{environment index identifiers}
	(see Section~\ref{environments}).
	This makes our environment declaration look like this:

\begin{verbatim}
environment node[N:id]
   {
   }
\end{verbatim}

\noindent
	So here is our code on the node environments:

\begin{quoteX}\begin{verbatim}
environment node[N:id]
   {
    composite mult(in A, in B, out C)
        float distributed A[N][N] map BlockRow;
        float distributed B[N] map all;
        float distributed C[N] map Block;
       {
        int I;

        C[id] = 0;
        for (I = 0; I < N; I++)
            C[id] += A[id][I] * B[I];
       }
   }
\end{verbatim}\end{quoteX}

\itemXblank Notice that the distributed data, particularly the arrays $A$ and
$C$, is referenced using its global
name\indexB{distributed data}{global name of},
even though only part of either of
these data structures is actually on each environment.  \dino\ automatically
handles this process.  However, if you try to reference some part of a
distributed data structure that is not on an environment, \dino\ isn't
so nice.  At this time, \dino\ does not check for these kind of mistakes
(it would require run-time checking\indexA{run-time errors} - see Section~\ref{run-time checking}).
At best, your program will crash.
At worst, you will get incorrect results.  So be careful of this.

	\itemX {Insert any necessary \underline{\em receives}.}
	\indexB{receives}{in matrix vector multiplication}

	There aren't any.

	\itemX {Insert the corresponding \underline{\em sends}.}
	\indexB{sends}{in matrix vector multiplication}

	There aren't any of these either.

	\end{itemizeX}

\itemX {Step 4 --- Finally, write a \underline{\em host environment},
containing a \underline{\em main() function} to implement
computation on the host environment.}
\indexB{host environment}{in matrix vector multiplication}
\indexB{main() function}{in matrix vector multiplication}

This turns out to be very straight forward.  All of this is ordinary C
code except the composite procedure
call\indexC{composite procedures}{calls}{in matrix vector multiplication}

\begin{quotation}\begin{verbatim}
mult(a[][], b[], c[])#;
\end{verbatim}\end{quotation}
\noindent
Note that since we are sending entire arrays (and not just pointers
to them), we use ranges (see section~\ref{subarrays and ranges}).

\end{itemizeX}

With this last part, our program is complete.  Here is the \dino\ code for
the whole thing:

\begin{quoteX}\begin{verbatim}
/*
 *      This does a matrix-vector multiply.  The
 *      limitations are that the matrix and vector
 *      sizes must be equal to the number of processors.
 *
 *      The basic algorithm is that a row of the
 *      matrix is sent to each processor and a copy
 *      of the vector is sent to each processor.
 *      Each processor does a dot product with its
 *      data and returns one element of the result.
 *
 */

#define N 16

#include "dino.h"

environment node[N:id]
   {
    composite mult(in A, in B, out C)
        float distributed A[N][N] map BlockRow;
        float distributed B[N] map all;
        float distributed C[N] map Block;
       {
        int I;

        C[id] = 0;
        for (I = 0; I < N; I++)
            C[id] += A[id][I] * B[I];
       }
   }

environment host
   {
    main()
       {
        int I, J;
        float a[N][N], b[N], c[N];

            /* Initialize the array and
                     the multiplicand vector to something. */

        for (I = 0; I < N; I++)
           {
            b[I] = 0.1;
            for (J = 0; J < N; J++)
                a[I][J] = (I + J) / 10.0;
           }

            /* Call the composite procedure. */

        (void) printf("\nStarting the computation . . . .\n\n");
        mult(a[][], b[], c[])#;

            /* Print out the results. */

        (void) printf("Results:\n");
        for (I = 0; I < N; I++)
           {
            if (I % 8 == 0)
                (void) printf("\n");
            (void) printf("   %6.2f", c[I]);
           }
        (void) printf("\n");
       }
   }
\end{verbatim}\end{quoteX}

\subsubsection{Matrix-Matrix Multiply}
\indexC{examples}{matrix matrix multiplication}{walkthrough}
\label{matrix matrix multiply}

This example takes a somewhat more complex problem than the last one, namely
a matrix-matrix multiply in which the sizes of the data structures can
be a multiple of the number of processors available, and shows how to
write the DINO program to compute the result.  In addition to
illustrating how to cope with the increased difficulty because (1) the
basic algorithm is somewhat more complex than the one in the last example
and (2) we are allowing multiple rows or columns in each processor, this
problems illustrates how to cope with the difficulty caused by a
problem that doesn't fit the \dino\ paradigm as well as other problems.

\begin{itemizeX}

\itemX {Step 0 --- Begin with a good understanding of the
problem and a general approach to its solution.}

The general algorithm for a matrix-matrix multiply is simple -- each element
of the solution matrix is obtained by taking the dot product of the
corresponding row and column of the two multiplicand matrices.  Our concern
here is to decide how to parallelize this problem.  We start off with three
square matrices -- two multiplicands and the solution.
Initially, we will try an
obvious approach:  block the first multiplicand by rows and send one
block to each processor.  If we block the answer in the same manner, we can
just collect the answer at the end of the computation.

The second multiplicand is more of a problem.  Initially, lets explore
what happens if we block it by columns, and send one block to each processor.
This allows us to compute part of the answer that is on each processor, but
not all of it.  A little thought and we realize that we will need all the
columns to compute our part of the answer.  Let us assume for now that we
will block the second multiplicand by columns and use \dino 's communications
to make the blocks available to all processors.

Now we might notice that although we are supposed to be thinking about
the parallel algorithm in general, we are influenced by the physical
constraints of the machine.  As we do more of these problems, we will
learn that we are also influenced by the nature of \dino.  In reality,
the process is an iterative one;  we may have to go through the four
``steps'' several times to obtain a good understanding of a particular
problem.

\vspace{12pt}
\vbox{
If we draw a picture of our algorithm we get something like:
\vspace{8pt}

\begin{tabular}{|l| l |l|l|l|l| l |l|} \cline{1-1} \cline{3-6} \cline{8-8}
 & & & & & & & \\
 & & & & & & & \\ \cline{1-1} \cline{8-8}
 & & & & & & & \\
\hspace{1.25in} & & \hspace{.2in} & \hspace{.2in} & \hspace{.2in} & \hspace{.2in} & & \hspace{1.25in} \\ \cline{1-1} \cline{8-8}
 & {\Large {\bf X}} & & & & & {\Large {\bf =}} & \\
 & & & & & & & \\ \cline{1-1} \cline{8-8}
 & & & & & & & \\
 & & & & & & & \\ \cline{1-1} \cline{3-6} \cline{8-8}
\end{tabular}
}

\itemX {Step 1 --- Choose a {\em structure of environments} appropriate to
the problem.}
\indexB{structure of environments}{in matrix matrix multiplication}

Given the way we have decided to break up our problem, a vector of
environments seems appropriate.  For efficiency, we will use a structure
of environments the size of the machine (which we assume to be 16).  So our
code initially looks like this:

\begin{quotation}\begin{verbatim}
environment node[P]
   {
   }
\end{verbatim}\end{quotation}

To make things easier to change, we will use macro definitions --- $P$ for
the size of the machine (16), and $N$ for the size of the arrays (256).

If we think about this decision a little, it might seem to make more sense
to use a torus instead of a vector.  That way when we go to ``shift'' each
block of columns to the left, we would not have to treat the ends of the
vector specially.  However, this particular feature is not implemented in
this version of \dino.

\itemX {Step 2 --- Determine how the principal data structures should be
distributed among the environments in the structure you have chosen
(specify the \underline{\em mappings}.)}
\indexB{mapping functions}{in matrix matrix multiplication}

	\begin{itemizeX}

	\itemX {Determine the basic \underline{\em partitioning}.}
\indexB{partitioning of data structures}{in matrix matrix multiplication}

	This seems easy enough.  Lets call our multiplicand matrices $A$
	and $B$ and our solution matrix $C$.  We block $A$ and $C$ by rows
	and $B$ by columns.

	\itemX {Determine any \underline{\em replication}.}
\indexB{replication of data structures}{in matrix matrix multiplication}

	There isn't any.

	\itemX {Determine where any \underline{\em copies}
	(used for communication) go.}
\indexB{copies in distributed data structures}{in matrix matrix multiplication}

	This may cause us problems.  What we really want to do is to take
	each block of columns and shift it one environment to the left for
	each iteration of the computation until every block has been to all
	of the environments.  But this is a different sort of communication
	than the \dino\ paradigm is designed to support (see
	Section~\ref{mapping philosophy});  \dino\ assumes that a
	particular piece of data has one ``home'' environment and other
	environments may have ``copies'' of the data.

	How could we get around this?  Here are two ideas that might come to
	mind: (1) place a copy of each block on every processor, or (2) place
	a copy of each block on the processor to its left and use that to shift
	the blocks.  Let us look at each of these ideas.

	The first of these ideas is quite easy to implement and would be easy
	to write code for.  But it has one serious drawback.  The compiler
	must create storage for the whole $B$ matrix on each environment if
	we do this.  Since, in this example, we are concerned about storage,
	this is not acceptable.  (Note, that this is equivalent to replicating
	$B$ across all the environments.)

	The second idea at first seems somewhat more workable.  We put a copy
	of each block on the environment to the left of it.  Then when we are
	ready to communicate, we assign the value of the copy data to the home
	data and send it.  (We can do this with a simple \dino\ statement like

\begin{quotation}\begin{verbatim}
B[][<my_first, my_last>]# =
               B[][<left_first, left_last>];
\end{verbatim}\end{quotation}

\noindent assuming ``{\tt my\_first}'', ``{\tt my\_last}'',
	``{\tt left\_first}'', and ``{\tt left\_last}'' are defined as we
	do later in this example to give the first and last columns in the
	current block and in the block to the left of us.)

	However, this leads to several difficulties that causes us to reject
	this approach: (1) we would have to be very careful how we reference the
	elements of $B$ since we are shifting the columns around but \dino\ is
	not aware of this so the global
	names\indexB{distributed data}{global name of} we would ordinarily
	use will
	not be correct (see more discussion on this point later); (2) we would
	have to handle the communications at the ends of the environment
	structure specially since we are unable to declare it to be a torus;
	(3) this would complicate the communications structure since there are
	two blocks already on each environment when we start up -- no
	communication needs to be done until the third iteration; and (4) we
	would double the storage necessary for $B$ on each environment.

	Well, when all else fails, there is a form of
	send\indexB{sends}{explicit} and receive\indexB{receives}{explicit} that
	puts everything in the hands of the
	programmer\indexA{explicit communication}.  We will fall back on
	that.  We will tell the compiler that we are just going to partition
	$B$ and then handle the communications ourselves.  That means we have
	to be more careful that we get everything right.  A future
	version of \dino\ may handle this particular problem better.

	\end{itemizeX}

\vspace{12pt}
\vbox{
\noindent
The mappings that give the partitioning we want are \bold{BlockRow} and
\bold{BlockCol}.  (We looked at the predefined \dino\ mappings to find this
information; see Section~\ref{predefined mapping functions}.)
Our declarations therefore look like:

\begin{quoteX}\noindent\begin{verbatim}
        float distributed A[N][N] map BlockRow;
        float distributed B[N][N] map BlockCol;
        float distributed C[N][N] map BlockRow;
\end{verbatim}\end{quoteX}
}

\itemX {Step 3 --- Write a \underline{\em composite procedure}
to implement computation in the structure of environments.}
\indexB{composite procedures}{in matrix matrix multiplication}

	\begin{itemizeX}

	\itemX {Write the code for the {\em computation}.}

	Initially, this seems pretty straight forward.  We have four loops:
	(1) the outermost keeps track of which column block of $B$ we have,
	(2) the next one is the row of $A$ that we are working on, (3) then
	there is which column within the particular column block of $B$ we
	have, and (4) finally there is a loop for doing the dot product
	itself.  There are several points to note:

		\begin{itemizeX}

		\itemX {Right away we realize we need some way of identifying
		which environment we are on.  Once again, we use an
		{\em environment index
		identifier}\indexA{environment index identifiers}.
		This makes our
		environment declaration look like this:}

\begin{quotation}\begin{verbatim}
environment node[P:id]
   {
   }
\end{verbatim}\end{quotation}

		\itemX {The non-standard communications we are using will
		cause us
		problems in referencing data if we are not careful.  Normally,
		distributed data is referenced by its global
		name\indexB{distributed data}{global name of}.
		So, for example,
		on {\tt node[0]} our first row is ``{\tt 0}'' and our last
		row is
		``{\tt 15}''.  Of course, we have to write an expression that
		is good on any environment so we would write the first row as
		``{\tt id * N/P}'' and the last row as
		``{\tt (id + 1) * N/P - 1}''.

		However, we have done something funny with the columns in $B$.
		We
		initially distributed them with a standard mapping, but then we
		``shift'' them around ``by hand'' instead of having \dino\
		do it.
		Since the compiler doesn't know what we are doing with the
		communications, it will no longer keep track of the correct
		global
		names of the columns of $B$ once we do the first shift.  We have
		to do that.  So elements of $B$ will have to be referenced
		differently
		than elements of $A$ or $C$.

		What we need to realize is that the current block of $B$ will be
		addressed in exactly the same manner on every iteration.  This
		is because the compiler doesn't think that anything has
		changed.  So,
		for example, when $B$ is first distributed, the first column on
		node[1] is ``{\tt id * N/P}'' (``{\tt 16}'') and the last column
		on node[1] is ``{\tt (id + 1) * N/P - 1}'' (``{\tt 31}'') -- the
		correct global names.  After the first shift, the first
		column is
		still ``{\tt id * N/P}'' and the last column is still
		``{\tt (id + 1) * N/P - 1}'', even though the correct
		global names
		are now ``{\tt 32}'' and ``{\tt 47}''.
		}

		\item For two reasons, it will be better if we define some
		intermediate values at the top of our program and compute them
		there: (1) it moves invariant expressions out of the loops (we
		know, good compilers are supposed to do this;
		but on the machines we've seen they don't), and (2) it makes the
		code much easier to read.
		So, for example, we define:

\begin{quotation}\noindent\begin{verbatim}
my_first = id * N/P;
my_last = (id + 1) * N/P - 1;
\end{verbatim}\end{quotation}
\vspace{12pt}
\noindent
		to take care of identifying the first and last row (column)
		on our environment.
		(We use the last instead of the last + 1 because we
		need that value in some range specifications.)
		For this problem,
		in addition to the two values above, we defined
		``{\tt left\_first}''
		(the first column on the environment to the left of us),
		``{\tt left\_last}'' (the last column on the environment to the
		left of us), ``{\tt left}'' (the index of the environment to the
		left of us), and ``{\tt right}'' (the index of the environment
		to the right of us).
		These last four we will use for communications.

		Notice that it is easier to code some of these calculations
		if we first write them for the ``middle,'' and then look at the
		edge cases.  For example, if we just look at the middle, then
		we would define \verb|left| as ``\verb|left = id - 1;|''.
		Then we look to see if there is anything different at either
		end.  It turns out that at node[0], we want \verb|left|
		to be equal to \verb|P - 1|, not \verb|-1|, so the definition
		of \verb|left| becomes
		``\verb|left = (id == 0) ? (P - 1) : (id - 1);|''.

		\end{itemizeX}
\vspace{12pt}
\noindent
	So here is our code on the node environments (except for the
	communications):

\begin{quoteX}\begin{verbatim}
environment node[P:id]
   {
    composite mult(in A, in B, out C)
        float distributed A[N][N] map BlockRow;
        float distributed B[N][N] map BlockCol;
        float distributed C[N][N] map BlockRow;
       {
        int I, J, K, L;
        int my_first, my_last, right,
                    left_first, left_last, left;

            /* Compute the environment indices of the
                       nodes on the right and left of me. */

        right = (id == P - 1) ? (0) : (id + 1);
        left = (id == 0) ? (P - 1) : (id - 1);

            /* Compute the starting and stopping
                         indices of the data in my block. */

        my_first = id * N/P;
        my_last = (id + 1) * N/P - 1;

            /* Compute the starting and stopping indices
                            of the data in the block of
                            the node to the left of me. */

        left_first =
            (id == 0) ? ((P - 1) * N/P) : ((id - 1) * N/P);
        left_last = (id == 0) ? (N - 1) : (id * N/P - 1);

        for (I = 0; I < P; I++)
           {
                /* Compute the values in the block of
                   C[][] that I currently have data for. */

            for (J = my_first; J < my_last + 1; J++)
                for (K = 0; K < N/P; K++)
                   {
                    C[J][K + ((id + I) * N/P) % N] = 0;
                    for (L = 0; L < N; L++)
                        C[J][K + ((id + I) * N/P) % N] +=
                               A[J][L] * B[L][K + my_first];
                   }
           }
       }
   }
\end{verbatim}\end{quoteX}

	\itemX {Insert any necessary \underline{\em receives}.}
\indexB{receives}{in matrix matrix multiplication}
\indexB{receives}{explicit}

	We want to put the receive as late as possible in the computation.
	We could do this by putting it just before the second loop (the
	``{\tt J}'' loop), but then we would have to put an if statement
	around it to insure that it only received from the second iteration
	on (since \dino\ initially distributes the data on the composite
	procedure call.  Instead we elect to put it at the end of the
	``{\tt J}'' loop.  Our receive will look like this:

\begin{quotation}\begin{verbatim}
B[][<my_first, my_last>] =
            B[][<my_first, my_last>]# {node[right]};
\end{verbatim}\end{quotation}

	We should note that we have to specify everything
	explicitly\indexA{explicit communication}.  In
	\dino, if we are using the default paradigm, the compiler does a lot
	of things for us.  The statement ``{\tt B[][<my\_first, my\_last>]\#;}''
	would cause the compiler to look for a piece of data with that name
	(in this context, ``name'' includes the bounds) and which came from
	the ``home'' environment of that particular piece of data.  When it
	found it, it would automatically store it in the correct location.
	When we go outside the default paradigm (by specifying the destination
	or source of the message), the programmer must specify it all
	explicitly.  ``All'' includes:

		\begin{itemizeX}

		\itemX {Where the incoming data will be placed
		(the specification on
		the left hand side of the assignment).}

		\itemX {The name of the incoming data (the part of the right
		hand side of the assignment that has the data name in it).}

		\itemX {The environment that the data is coming from.}

		\end{itemizeX}

	\itemX {Insert the corresponding \underline{\em sends}.}
\indexB{sends}{in matrix matrix multiplication}
\indexB{sends}{explicit}
\indexC{explicit communication}{sends}{in matrix matrix multiplication}

	We have two concerns here: (1) we want to assure that there are
	sends corresponding to every receive in the program (otherwise we
	either generate extra messages which can cause problems in a large
	program or we never get a message we are looking for and the
	program locks up), and (2) we want to put the send as early as
	possible in the computation.

	The first of these can be complex, because there is not always a
	one-to-one relationship between the number of sends and the number
	of receives (in \dino\ you can send a range of data and the compiler
	will actually do a send to more than one environment; the same is
	true for receives).  However, that is not the case here. So we
	just have to be sure there is a send for each receive.  We insure
	that if the send and receive are in the same loop.

	The second of these concerns is satisfied if we place the send at
	the beginning of the ``{\tt J}'' loop.  Then our send looks like
	this:

\begin{quotation}\begin{verbatim}
B[][<left_first, left_last>]#{node[left]} =
                          B[][<my_first, my_last>];
\end{verbatim}\end{quotation}
\noindent
	Some points to notice on this:

		\begin{itemizeX}

		\itemX {We have to explicitly include the same things in this
		kind of send that we did in the corresponding receive.}

		\itemX {The name of the data must be the same in the send as the
		receive.  Because the expression for the range endpoints
		uses ``{\tt id}'' (which is different on each environment),
		the expressions have to be different for the send and receive
		to give us the same name.
		This accounts for using ``{\tt left\_first}'' and
		``{\tt left\_last}'' to send the data but ``{\tt my\_first}''
		and ``{\tt my\_last}'' to receive it.}

		\end{itemizeX}

	\end{itemizeX}

\noindent
	The computation loop (with all communication statements inserted)
	looks like:

\begin{quoteX}\begin{verbatim}
        for (I = 0; I < P; I++)
           {
                /* First, send out the data that the node on
                   the right of me will need next iteration. */

            B[][<left_first, left_last>]#{node[left]} =
                                      B[][<my_first, my_last>];

                /* Then, compute the values in the block of
                       C[][] that I currently have data for. */

            for (J = my_first; J < my_last + 1; J++)
                for (K = 0; K < N/P; K++)
                   {
                    C[J][K + ((id + I) * N/P) % N] = 0;
                    for (L = 0; L < N; L++)
                        C[J][K + ((id + I) * N/P) % N] +=
                                    A[J][L] * B[L][K + my_first];
                   }

               /* Finally, receive the data from the node on
                  the right that I need for the next iteration. */

            B[][<my_first, my_last>] =
                        B[][<my_first, my_last>]#{node[right]};
           }
\end{verbatim}\end{quoteX}

The astute observer will notice that there is an extra send/receive pair in
this loop.  We do not need to do the send/receive on the last iteration since
there will not be a next iteration to use the new data.  However, it would
have required two additional if statements to remove this, which for large
matrices would slow the program down more than the additional send/receive
pair.

\itemX {Step 4 --- Finally, write a \underline{\em host environment},
containing a \underline{\em main() function} to implement
computation on the host environment.}
\indexB{host environment}{in matrix matrix multiplication}
\indexB{main() function}{in matrix matrix multiplication}

This turns out to be very straight forward.  All of this is ordinary C
code except the composite procedure
call\indexC{composite procedures}{calling}{in matrix matrix multiplication}

\begin{quotation}\begin{verbatim}
mult(a[][], b[][], c[][])#;
\end{verbatim}\end{quotation}

\noindent
Note that since we are sending entire arrays (and not just pointers
to them), we use ranges (see Section~\ref{subarrays and ranges}).

\end{itemizeX}

\noindent
With this final step, our program is done.  Here is the \dino\ code for
the complete program:

\begin{quoteX}\begin{verbatim}
/*
 *      This program does a matrix-matrix multiply.  The
 *      only limitations are that the matrices must be
 *      square and that their size must be a multiple of
 *      the number of processors.
 *
 *      The basic algorithm is to block the first matrix
 *      by rows and send a block to each processor, and
 *      block the second matrix by columns and send a block
 *      to each processor.  Each processor computes the
 *      results for that sub-matrix for which it has data
 *      and then the blocks of columns are all shifted to
 *      the right one processor.
 *
 */

#define N 256
#define P 16

#include "dino.h"

environment node[P:id]
   {
    composite mult(in A, in B, out C)
        float distributed A[N][N] map BlockRow;
        float distributed B[N][N] map BlockCol;
        float distributed C[N][N] map BlockRow;
       {
        int I, J, K, L;
        int my_first, my_last, right,
                    left_first, left_last, left;

            /* Compute the environment indices of the
                       nodes on the right and left of me. */

        right = (id == P - 1) ? (0) : (id + 1);
        left = (id == 0) ? (P - 1) : (id - 1);

            /* Compute the starting and stopping
                         indices of the data in my block. */

        my_first = id * N/P;
        my_last = (id + 1) * N/P - 1;

            /* Compute the starting and stopping indices
                            of the data in the block of
                            the node to the left of me. */

        left_first =
            (id == 0) ? ((P - 1) * N/P) : ((id - 1) * N/P);
        left_last = (id == 0) ? (N - 1) : (id * N/P - 1);

        for (I = 0; I < P; I++)
           {
                /* First, send out the data that the node on
                   the right of me will need next iteration. */

            B[][<left_first, left_last>]#{node[left]} =
                                      B[][<my_first, my_last>];

                /* Then, compute the values in the block of
                       C[][] that I currently have data for. */

            for (J = my_first; J < my_last + 1; J++)
                for (K = 0; K < N/P; K++)
                   {
                    C[J][K + ((id + I) * N/P) % N] = 0;
                    for (L = 0; L < N; L++)
                        C[J][K + ((id + I) * N/P) % N] +=
                                    A[J][L] * B[L][K + my_first];
                   }

               /* Finally, receive the data from the node on
                  the right that I need for the next iteration. */

            B[][<my_first, my_last>] =
                        B[][<my_first, my_last>]#{node[right]};
           }
       }
   }

environment host
   {
    main()
       {
        int I, J;
        float a[N][N], b[N][N], c[N][N];

            /* Initialize the two
                        multiplicand arrays to something. */

        for (I = 0; I < N; I++)
            for (J = 0; J < N; J++)
               {
                a[I][J] = 0.1;
                b[I][J] = (I + J) / 10.0;
               }

            /* Call the composite procedure. */

        (void) printf("\nStarting the computation . . . .\n\n");
        mult(a[][], b[][], c[][])#;

            /* Print out the results -- because the data
                we use generates the same answer for each element
                in any column, we only print out the first row. */

        (void) printf("Results:\n");
        for (I = 0; I < N; I++)
           {
            if (I % 8 == 0)
                (void) printf("\n");
            (void) printf("   %6.2f", c[0][I]);
           }
        (void) printf("\n");
       }
   }
\end{verbatim}\end{quoteX}

\vbox{
\sectionX{\protect\dinoB\ --- The Language}
\label{language reference}
\indexA{program structure}

This section contains the formal definition of \dino.
It is broken down into the major categories of \dino\ constructs:
program structure, environments, composite procedures, distributed data,
reduction functions, ranges, and user defined mappings.
If the meanings of the \ebnf\ specifications used here are unfamiliar,
an explanation can be found in Appendix~\ref{ebnf}.

\subsectionX{Program Structure}\indexA{program structure}
\begin{verbatim}
PROGRAM ::= (ENVIRONMENT or MAPPING_FUNCTION or DATA_DEFINITION )+.
\end{verbatim}
}

A program consists of one or more environment declarations\indexA{environments},
zero or more mapping function\indexA{mapping functions}
declarations, and zero or more (distributed) data declarations.
One of the environment declarations must be defined as a scalar environment
with the name ``host''\indexA{host environment}. 
This environment must contain a function, named
``main''\indexA{main() function}, where execution starts.  
The remaining environment declarations
generally define structures of environments that contain composite
procedures which are invoked from the host.

Distributed data structures that are declared at the program
level\indexB{distributed data}{at program level} are mapped
to one or more environment structures in the program
as specified by their mapping functions.\indexA{mapping functions}
Ordinary data declarations\indexB{nondistributed data}{at program level}
can also be made at this level.
\indexB{ordinary data declarations}{at global level}
If they are,
independent copies are instantiated on every environment in the program.
Mapping functions that are declared at the program level are
accessible to all parts of the program.
The normal C rule that requires definition before use is followed throughout
\dino.  

\subsectionX{Environments}\indexA{environments}
\label{environments}

\vbox{
\begin{verbatim}
ENVIRONMENT ::=
    `environment' IDENTIFIER DIMENSION*
    `{' EXTERNAL_DEFINITION+ `}'.

DIMENSION ::= `[' EXPRESSION [ `:' IDENTIFIER ] `]'.

EXTERNAL_DEFINITION ::=
    FUNCTION_DEFINITION | DATA_DEFINITION | MAPPING_FUNCTION.
\end{verbatim}
}

A structure of environments\indexA{structure of environments}
provides a virtual parallel machine,
and a mechanism for building parallel algorithms in a top down fashion.
An environment may contain composite procedures, standard C functions,
distributed data declarations, standard C data declarations,
and mapping functions. 
Each environment within a given structure contains the same procedures,
functions, and C data declarations, and shares the same distributed
data declarations.

A structure of environments may be any single or multiple dimensional array. 
For example, the declaration

\begin{quotation}\begin{verbatim}
environment grid [N:xid] [M:yid]  {  . . .  }
\end{verbatim}\end{quotation}

\noindent
specifies an $N$ by $M$ array of virtual processors\indexA{virtual processors}
named ``grid''.
In order to give each environment within a structure an identity
that can be used in calculations, 
the programmer can declare 
constants that will contain the subscripts 
identifying that particular environment.
These are referred to as \underline{\em environment index identifiers}.
\indexA{environment index identifiers}
In the above example, these are ``xid'' and ``yid''.
Most often these are used to refer to that environment's portion of
a distributed data structure, for example a matrix element $A[xid][yid]$. 

A \dino\ program may contain any number of environment declarations.
Typically only one, the host,\indexA{host environment} is
scalar\indexB{environment structures}{scalar environments}, and the
remainder are arrays.
Multiple structures of environments may be used when successive
phases of a computation map naturally onto different parallel machines
(in this case, generally only the environments in one structure become
active at once)
or in functionally parallel programs\indexA{functional parallelism}
(in this case the environments in multiple structures  
become active at the same time; see Section~\ref{composite procedures}).

An environment can contain an arbitrary number of composite procedures
and standard C functions.
However only one task,\indexA{single task semantics}
or thread of control,\indexA{thread of control}
may be active in an environment at a time.
We refer to this as \underline{\em single task semantics}.
In addition, the only way to start a task
executing in an environment other than the host is to call a composite 
procedure which resides in that environment.  
These two facts imply that there 
can not be any composite procedures in the host environment because procedure 
``main''\indexA{main() function} is always active.

A procedure executing in one environment can not directly reference data in
another environment.  
Procedures in two environments can exchange 
information only if there is cooperation between the procedures,
namely a remote read and write of a distributed variable,
\indexA{distributed data} (Section~\ref{using distributed data})
or the use of a reduction\indexA{reductions} operator
on a distributed variable (Section~\ref{reduction functions}). 
These semantics and the single task semantics\indexA{single task semantics}
described above
imply that there is is no hidden shared-memory emulation in \dino\,
and also results in \dino\ programs being deterministic\indexA{determinism}
unless asynchronous distributed variables\indexB{distributed data}{asynchronous}\indexA{``asynchronous'' keyword} or
explicit environment
sets\indexB{explicit communication}{environment expressions}\indexA{environment expressions}
are used (see Section~\ref{distributed data}).

Structures of environments are treated as blocks with respect to scope.
\indexB{scoping}{of environment structures}
Ordinary data\indexB{ordinary data}{at environment level}
that is declared within an environment structure
is copied to every environment in that structure.
Copies of ordinary data on separate environments have no relation
to each other and can only be accessed within their own environments.
Distributed data is treated as described in Section~\ref{distributed data}.
The one exception to this scoping rule is composite
procedures,\indexB{scoping}{of composite procedures} which
are always visible in the topmost scope.
Thus composite procedures may be called
from any environment except their own, 
i.e. recursive calls are not allowed.

The \dino\ compiler creates one process for every environment in each
structure\indexB{environment structures}{mapping onto real processors}
\indexB{virtual processors}{mapping onto real processors}
and maps these processes statically onto the actual parallel machine.
This is done in a manner that attempts to optimize the distance 
on the parallel computer
between contiguously indexed environments in each structure.
\indexB{environments}{mapping to real processors}
The mapping also attempts to optimize load balance as follows:
if any structure of environments contains as many or more environments than
there are actual processors, then 
the environments are partitioned evenly over
the entire parallel machine. 
When a composite procedure is invoked
in a structure with more environments than 
processors, multi-programming occurs.\indexA{multi-programming}
This style of programming does not lead to optimal efficiency
and may not run due to memory limitations (see
Section~\ref{performance hints}). 
If there are two or more structures of one dimensional
environments that together
contain no more environments than the total number of processors,
then each environment is assigned to a unique processor. 

\vbox{
\subsectionX{Composite Procedures}
\indexA{composite procedures}
\indexB{composite procedures}{calling}
\indexB{composite procedures}{declaration}
\label{composite procedures}
\begin{verbatim}
declaration:

FUNCTION_DEFINITION ::=
    `composite' IDENTIFIER `(' [COMP_PARAMETER_LIST] `)'
    FUNCTION_BODY.

COMP_PARAMETER_LIST ::= ( [`in' | `out'] IDENTIFIER ) || `,'.

call:

STATEMENT ::=
    IDENTIFIER `(' [EXPRESSION_LIST] `)' `#' [ `{' ENV_EXP `}' ]
    [ `::' STATEMENT ].

ENV_EXP ::= EXPRESSION.
\end{verbatim}
}

A composite procedure is a procedure which runs on each environment of a
structure of environments (or a subset thereof)
and thereby implements concurrency.\indexA{concurrency}
A composite procedure
consists of multiple copies of the same procedure, one residing within each
environment of a structure of environments.  
Calling the composite procedure invokes
all of these procedures at the same time.  
Typically, each procedure works on a 
different part of some distributed data structure(s),
resulting in a single program, multiple data ({\small SPMD})\indexA{SPMD}
form of parallelism.  
These distributed data structures\indexA{distributed data structures}
may either be defined in the structure of environments or globally 
or may be parameters to the composite procedure.  
Each procedure may also contain standard local data.
We will first describe the various parts of composite
procedure declaration and invocation statements, and then the order of
events that occur when a composite procedure is invoked.

The formal parameters\indexB{composite procedures}{formal parameters}
of a composite procedure
may be distributed
variables\indexB{distributed data}{as formal parameters to composite procedures}
or standard variables.
Formal parameters that are distributed variables may be preceded by the 
keywords ``in'' (call-by-value),\indexA{``in'' keyword (call by value)}
``out'' (call-by-result),\indexA{``out'' keyword (call by result)}
or no keyword (call-by-value/result).
Formal parameters that are standard variables must be preceded by ``in''
\indexB{nondistributed data}{as formal parameters to composite procedures}
\indexB{``in'' keyword (call by value)}{use with nondistributed variables}
and are input parameters that are
replicated\indexB{replication of data structures}{of nondistributed parameters to composite procedures}
in all the environments on which the composite procedure is called.

A composite procedure call has the same syntax
as ordinary C functions, except
that arrays or subsections of arrays (Section~\ref{subarrays and ranges})
and remote references to distributed variables can be used as arguments,
and the parameter list is followed by a ``\#''
sign.\indexB{``\#'' sign}{in composite procedure calls}
All actual parameters corresponding to result and value/result
parameters must refer to variables.  
Unlike C, \dino\ checks the number and
types of actual parameters against the formal parameters
in a composite procedure call.  
Composite procedures do not return a value.

When a composite procedure is called, the invocation can be limited to a
subset of the environments in the environment structure
on which it is defined.  
This is accomplished
using the optional \envexp\indexA{environment expressions (envexp's)}
following the ``\#'' sign, which
returns a subset of environments on which the
procedure is to be invoked (the
``active-set''\indexB{active-set}{in composite procedure calls}%
\indexC{composite procedures}{calling}{with an active-set}).  
The form of \envexp\ is one
or more environment names (or ranges --- see
Section~\ref{subarrays and ranges})
connected by set union or difference operators ``+'' and ``--''.
If this expression is not given, then the composite
procedure is invoked on all of the environments in the structure. 

Functional parallelism\indexA{functional parallelism}
is achieved in \dino\ by the utilization of the
optional 
\mbox{``::~\small STATEMENT''}\indexA{``::''}
construct following a composite procedure call 
(this definition is recursive; see the \ebnf\ specification
in Appendix A).
This {\small STATEMENT} is executed concurrently\indexA{concurrency}
with the composite procedures
specified by the call.  
It can be either another
composite procedure call utilizing a different structure of environments
(or a disjoint subset of the same structure),
or a standard C statement that is executed on the host.
The program blocks until both the composite procedure and
the concurrent statement complete execution.

The keyword ``caller'',\indexA{``caller''}
when used within a composite procedure, is the
environment which invoked that composite procedure.
This may be used 
when a composite procedure is executing concurrently with code on the
invoking environment, as described in the previous paragraph,
and wants to communicate with the procedure that invoked it
via explicit reads and writes of global distributed data
(see Section~\ref{using distributed data}).

Now we describe in detail the events that occur 
when a composite procedure is invoked.
First, the \envexp\ expression is evaluated if it is given.  
This defines
an active-set of environments as described above.  
Only procedures and
environments in the active-set are used in the rest of the sequence.
Second, all of the actual parameters that correspond to value and
value/result formal parameters are evaluated.  
If any of these actual
parameters contains a ``\#'' operator then a remote read
is executed to get the value (see Section~\ref{using distributed data}).  
Third, the values of the actual parameters are assigned to
the formal parameters and sent to the appropriate environments.  
For formal
parameters that are not defined as ``distributed'', 
the actual parameter value is
sent to each environment in the active-set. 
If the formal parameter is
defined as ``distributed'' then the actual parameter 
value is distributed to each
environment that it is mapped to (but limited to the active-set).  
Fourth, the procedure is actually called
at each environment in the active set.  
At the same time,
the concurrent {\small STATEMENT}, if any,
is executed in the calling environment
(possibly resulting in one or more additional composite procedure calls 
on different environments).  
Fifth,
after all these procedures/{\small STATEMENT}s have completed executing, the
result and value/result parameters are returned.  
Each element
of a result parameter is returned from exactly one environment,
its ``home'' environment (see Section~\ref{home and copy data}).  
If any of these actual parameters contains a ``\#'' operator then
a remote write is be executed.  
Finally, the calling environment
continues execution after the concurrent {\small STATEMENT}.

{\samepage
\subsectionX{Distributed Data}\indexA{distributed data}
\label{distributed data}

Distributed data is used to map data structures onto
the structures of environments in a \dino\ program.
It provides the mechanism for
communication\indexB{communication}{using distributed data}
between environments, 
which is accomplished by using distributed
variables as formal parameters to composite procedures, and by remote
references to distributed variables.
It also allows the programmer to maintain a global view of 
these data structures\indexB{distributed data}{global view of}
(in most situations; see
Section~\ref{matrix matrix multiply})
and joins with composite procedures
to produce an {\small SPMD}\indexA{SPMD} model of computation.
}

Currently, the types of data structures
that can be distributed are arrays of any dimension.
\dino\ provides a rich mechanism for specifying the mappings
of such data structures onto structures of environments,
including many different one-to-one and one-to-many mappings,
and also provides efficient implementation of the communication
that can result through the use of these variables.
The declaration of distributed data is discussed in
Section~\ref{distributed data - declaration}.
Section~\ref{predefined mapping functions} discusses the predefined
mapping functions in the include file ``dino.h''.
In Section~\ref{home and copy data}, the concepts of home and copy data
are discussed.
The use of distributed data, primarily remote references
for communication, is discussed in Section~\ref{using distributed data}.

\vbox{
\subsubsectionX{Declaring Distributed Data}
\label{distributed data - declaration}
\indexB{distributed data}{declaration of}

\begin{verbatim}
distributed data declaration:

DECLARATOR ::=
    [ `asynch' ] `distributed' DECLARATOR
    ( `[' CONSTANT_EXPRESSION `]' )+ MAPPING.

MAPPING ::=
    `map' (`all' | IDENTIFIER | (( IDENTIFIER IDENTIFIER ) || `map')).
\end{verbatim}
}

Distributed data declarations follow standard C syntax,
except that the keyword ``distributed''\indexA{``distributed'' keyword}
precedes the name of the distributed variable, 
and the keyword ``map''\indexA{``map'' keyword} followed by the name
of a mapping function follows it.
An example is
\begin{quotation}\begin{verbatim}
float distributed A[N][N] map BlockRow;
\end{verbatim}\end{quotation}
Distributed data may be declared 
at any level of a \dino\ program,
and follows standard C scoping rules.
The {\tt MAPPING} portion of a distributed data
declaration\indexB{distributed data}{shared between multiple environments}
that is not contained in an environment declaration must use the
``{\tt IDENTIFIER IDENTIFIER \verb$||$ `map'}''
syntax, where the
second identifier in each pair is an environment name:

\begin{quotation}\begin{verbatim}
float distributed A[N][N] map grid BlockBlock map node BlockRow
\end{verbatim}\end{quotation}

\noindent
The mapping function(s) are either taken from \dino 's library of
predefined mapping functions,\indexB{mapping functions}{predefined}
as is the case with \bold{BlockRow} and \bold{BlockBlock} above, 
or is defined by a mapping function definition statement
(see Section~\ref{mapping definition}).

\subsubsectionX{Predefined Mappings}
\label{predefined mapping functions}
\indexB{mapping functions}{predefined}

\dino\ provides a set of predefined mapping functions for mapping
one and two dimensional (hereafter ``1D'' and ``2D'')
data structures onto 1D structures of environments,
and 2D data structures onto 2D structures of environments.
The predefined 1D to 1D mappings are
\begin{quotation}
\bold{Block}, \bold{Wrap}, and \bold{BlockOverlap}.
\end{quotation}
They can be used to map any array of $N$ elements
onto an array of $P$ environments, and work in a fairly obvious way.
If $N$ is a multiple of $P$, then
\bold{Block}\indexB{mapping functions}{Block} maps the first $N/P$ data elements
onto the first environment, and so on;
if $N<P$ then the first $N$ environments contain one element
each and the last $N-P$ contain none,
while if $N>P$ but $N$ is not a multiple of $P$,
then the first $N \bmod P$ environments contain an extra element.
\bold{Wrap}\indexB{mapping functions}{Wrap} maps each element
$i~ (i=0,\cdots,N-1)$ to environment [$i \bmod P$].
\bold{BlockOverlap}\indexB{mapping functions}{BlockOverlap}
does a \bold{Block} mapping and in addition, maps
the first and last elements of each block (except elements
$0$ and $N-1$) to the next lower and higher environment, respectively.
This extra mapping is referred to as an
\underline{\em overlap}\indexA{overlaps}\indexB{mapping functions}{overlaps}
(One-sided overlaps and wider overlaps are
also possible using user-defined mappings; see
Section~\ref{user defined mappings}).

The predefined mappings for mapping 2D ($M$ x $N$) data structures to 
1D ($P$) environment structures are
\begin{quotation}
\bold{BlockRow},\indexB{mapping functions}{BlockRow}
\bold{BlockCol},\indexB{mapping functions}{BlockCol}
\bold{WrapRow},\indexB{mapping functions}{WrapRow}
\bold{WrapCol},\indexB{mapping functions}{WrapCol}
\bold{BlockRowOverlap},\indexB{mapping functions}{BlockRowOverlap}
and \bold{BlockColOverlap}.\indexB{mapping functions}{BlockColOverlap}
\end{quotation}
They work identically to the above 1D to 1D mappings except that
rows or columns are used in the place of individual elements. 
For mapping 2D ($M$ x $N$) data structures onto  
2D ($P$ x $Q$) environment structures, the predefined mapping functions are
\begin{quotation}
\bold{BlockBlock}, \bold{FivePt}, and \bold{NinePt}.
\end{quotation}
\bold{BlockBlock}\indexB{mapping functions}{BlockBlock}
divides the $M$ x $N$ array into sub-arrays of size
$M/P$ x $N/Q$ on each environment.
\bold{FivePt}\indexB{mapping functions}{FivePt} is a \bold{BlockBlock} mapping
with overlaps in the four directions;
in the case when $M=P$ and $N=Q$ it reduces to the standard five point
star (element $[i][j]$ mapped on to environments $[i-1][j]$,
$[i+1][j]$, $[i][j]$, $[i][j-1]$, and $[i][j+1]$, and visa versa.)
\bold{NinePt}\indexB{mapping functions}{NinePt} is a \bold{FivePt} mapping
where in addition the corner
elements are included in the overlap (in the $M=P$, $N=Q$ case these are
$[i-1][j-1]$, $[i-1][j+1]$, $[i+1][j-1]$, and $[i+1][j+1]$.)
Finally, the mapping keyword \bold{all}\indexB{mapping functions}{all}
maps all the elements of any dimensional data structure onto
each environment of any dimensional structure of environments.

\subsubsectionX{``Home'' and ``Copy'' Data}
\label{home and copy data}
\indexA{home data}
\indexA{copy data}

Implicitly associated with each mapping function is the specification
of one ``home'' environment,\indexB{distributed data}{home environment}
and zero or more ``copy''
environments,\indexB{distributed data}{copy environments}
for each element of the distributed data structure.
These constructs have an effect when distributed data structures
are parameters to composite procedures (see Section~\ref{composite procedures})
and in remote references to distributed data
(Section~\ref{using distributed data}).
If an element of a distributed data structure
is mapped to only one environment,
this is its home.
If it is mapped to multiple environments, this must be done
using either overlaps\indexA{overlaps}\indexB{mapping functions}{overlaps}
or the ``all'' construct.\indexA{all}\indexB{mapping functions}{``all'' keyword}
With overlaps, the home environment is the environment that the
data element would be mapped to if the overlap term was omitted,
while the additional environments that the overlap term causes it
to be mapped to are its copy environments.
If an element is mapped using ``all'', then 
we arbitrarily consider the lowest
subscripted environment to be its home and the
remainder to be copy environments, but this distinction is generally
unimportant since such variables are usually either input-only
parameters, or uniformly shared variables internal to the composite procedure.
The semantics of home and copy environments assure that \dino\
programs are deterministic\indexA{determinism}
in the default case (see Section~\ref{using distributed data}).

\vbox{
\subsubsectionX{Using Distributed Data}\indexB{distributed data}{use}
\label{using distributed data}

\begin{verbatim}
EXPRESSION ::= PRIMARY `#' [ `{' ENV_EXP [ `from' EXPRESSION ] `}' ].

ENV_EXP ::= `caller' | EXPRESSION.
\end{verbatim}
}

There are three different ways to use a distributed variable. 
The first is as a formal parameter to a composite procedure call,
as discussed in Section~\ref{composite procedures}.
The other two are by local and remote references (either reads or writes),
appearing as expressions in any standard C statement.

A local reference\indexB{distributed data}{local reference of}
of a distributed variable uses standard C syntax
and is the same as referencing any regular variable.  
The value of
the variable is retrieved from, or stored into, the local copy.  
This implies that the 
variable being referenced must be mapped to the environment in which the
reference is made.

A remote reference,\indexB{distributed data}{remote reference of}
either a read or a write, involves
communication between environments.
It is indicated by the distributed variable name (and subscripts, if any),
followed by a ``\#'',\indexB{``\#'' sign}{in remote references}
optionally followed by an explicit specification of the set of environments
to communicate with for this
reference.\indexB{environment expressions}{in remote references}
If this set is not provided explicitly, it is defined implicitly
by the mapping function\indexB{environment sets}{in remote references}
to be the set of all environments to which the
given subrange of the distributed variable is mapped.
The implicit environment specification is
usually sufficient,
and is considered
preferable because it is more structured and because
there is less likelihood of coding error. 

We first describe the semantics of remote references in the case where
the environment set is specified
implicitly\indexB{environment set}{implicit specification}
(by the associated mapping function).
These references basically follow the convention that the
home environment produces new values and the copy
environments consume them.

If the remote reference is a read\indexB{receives}{implicit environment set}
and the current environment is a
copy environment, then \dino\ looks for the 
first (least recent) value of that variable
that has been received from the home environment
but not yet utilized
(a message buffer is maintained, and the oldest message 
from the home environment 
with a value of that variable is used, and then removed
from the buffer.)  
If no new value of that variable
has been received from the home environment, 
the reading process blocks until one is received.  
When the new value is available, it is used to update the local copy
of the variable,
and then the remainder of the expression in which the remote read is
located is evaluated using the local copy.
If the remote reference is a read and the current environment is a home
environment, then the remote read is the same as a local read
(with some performance degradation,) and may produce a
run-time warning message (see Section~\ref{run-time checking}.)
If the current environment is neither a home nor a copy environment,
then a remote read is an error.

A remote write\indexB{sends}{implicit environment set}
to a distributed variable 
using an implicit environment set works as follows.
If the current environment is the home
environment of that variable 
and there are associated copy environments, then the value being
assigned to that variable is used to update the local copy
(since the write occurs in an assignment context), 
and also is sent to all the copy environments.
If the current environment is the home
environment and there are no associated copy
environments, then the remote write is treated as a local write
(again, there is some performance degradation).  
If the current environment is not the home environment, 
then an implicit remote write is an error.

As example of remote reads and a remote write,
consider a 2-dimensional smoothing algorithm
where an $N$ x $M$ distributed array of data $A[][]$ is mapped onto
an $N$ x $M$ array of virtual processors ``grid'', 
with each $A[i][j]$ mapped
onto $grid[i][j]$ (its home environment)
and the 4 adjoining
environments 
(this is the mapping function FivePt.)
Then the statement 
\begin{quotation}\begin{verbatim}
A[i][j]# = (A[i-1][j]# + A[i][j-1]# + A[i][j]
            + A[i][j+1]# + A[i+1][j]#)/5;
\end{verbatim}\end{quotation}
will receive values of the 4 adjoining elements of $A[][]$ from
their home environments, calculate the average of these four
values plus the local value, assign this new value to the local 
copy of $A[i][j]$, and send it to the 4 adjoining environments.

If the programmer wishes to send or receive distributed variables 
in a different manner than by these implicit
rules,\indexB{environment expressions}{in remote references}%
\indexB{environment sets}{in remote references}
a set of environments --- \envexp\
in the \ebnf\ specification above --- can be specified after
the ``\#'' sign.
\envexp\ uses the same
syntax as was discussed for it in Section~\ref{composite procedures}.  
For example,
\begin{quotation}\begin{verbatim}
grid[][] - grid[xid][yid] - grid[1][2]
\end{verbatim}\end{quotation}
specifies all the environments in the grid environment
structure except the environment that the statement is executed
in and $grid[1][2]$.
In contrast to remote references with implicit environment sets, 
the distributed variable does not need to be mapped to the
environment where the statement is executed.

A remote read with an explicit environment
set\indexB{receives}{explicit environment set}%
\indexB{environment expressions}{in receives}
is processed as follows.
The process looks for
the oldest unutilized value of that distributed variable
that has been received from 
any node in the environment set, 
including itself if it is in the set,
and blocks if no new value is available.
Once a value is received, it is used in 
evaluating the remainder of the expression.
(Note that the execution may be non-deterministic
if there is more than one environment in the set.)  

For a remote write with an explicit environment
set,\indexB{sends}{explicit environment set}%
\indexB{environment expressions}{in sends}
the new value of the variable is sent to all
of the environments in the environment set,
including itself if it is in the set.
Note that explicit references to variables that are mapped to the
local environment have different semantics than in the implicit case:
they do generate messages and do not 
automatically update the local copy or default to local reference.

After a remote read where the environment set 
was specified explicitly and contained
more than one element, 
it may be unknown which environment the new value came from.  
In order to obtain this information, 
the ``from''\indexA{``from'' keyword}%
\indexB{receives}{with ``from'' construct}%
\indexA{envvar (type used with ``from'')}
construct may be used.
The keyword ``from''
is appended to the environment set specification,
and is followed by a variable of type ``envvar''.  
For example, the statements

\vbox{
\begin{quotation}\noindent\begin{verbatim}
envvar who;
	...
w = x # {grid[][] from who};
	...
y # {who} = z;
\end{verbatim}\end{quotation}
}

\noindent
receive the value of $x$ from some  
environment in the structure ``grid'',
assign the name of this environment to $who$,
and later send the value of $z$ to the
environment that the value of $x$ was received from.  

All of the above discussion pertains to ``synchronous''
distributed variables, which are the default in \dino.
Distributed variables can also be declared to be
``asynchronous''\indexB{distributed data}{asynchronous}%
\indexA{``asynch'' keyword}
by placing the word ``asynch'' before ``distributed''
in their declarations.
The difference between synchronous and asynchronous variables 
is that a remote read to an asynchronous variable 
uses the most recent value and does not block.  
If several values of the variable
have been received since the last remote read,
then the most recently received value is used
to update the local copy and the remaining values are discarded.  
If no new value 
has arrived since the last remote read, then the local copy is used.
In keeping with these rules, an explicit remote read of an asynchronous
variable requires that the variable be mapped to the current environment.  
The remaining semantics of remote references to asynchronous variables,
including all the semantics for a remote write, 
are the same as for synchronous distributed variables.

By making the distinction between synchronous and asynchronous
communication part of the distributed variable declaration, as opposed
to a property of the statement that invokes communication,
it is possible to transform a \dino\ program from a synchronous
to an asynchronous variant by simply changing one or a few declarations.
Clearly, the execution of algorithms 
containing asynchronous variables may be non-deterministic.

\vbox{
\subsection{Reduction Functions}
\label{reduction functions}
\indexA{reductions}

\begin{verbatim}
PRIMARY ::=
    REDUCTION `(' EXPRESSION [ `,' EXPRESSION ] `)' `#'
    [ `{' ENV_EXP `}' ].

REDUCTION ::=
    `gsum' | `gprod' | `gmin' | `gmindex' | `gmax' | `gmaxdex'.
\end{verbatim}
}

One type of calculation that involves communication is so fundamental
to parallel computation, and departs sufficiently from simple
patterns of communication, that we have included it as 
a parallel language construct.
This is a reduction operation, which involves performing a 
commutative operation (e.g. +, *, min, max) over one value
from each environment and returning the result
to all the environments.
\dino\ provides the reduction operators
``gsum'',\indexB{reductions}{gsum()}\indexA{gsum() reduction function}
``gprod'',\indexB{reductions}{gprod()}\indexA{gprod() reduction function}
``gmax'',\indexB{reductions}{gmax()}\indexA{gmax() reduction function}
and ``gmin''\indexB{reductions}{gmin()}\indexA{gmin() reduction function}
that return the sum, product, maximum, or minimum
of the arguments specified on each environment.
For example, if {\tt error} and {\tt maxerror}  
exist on each environment in the current active set,
then the statement

\begin{quotation}\begin{verbatim}
maxerror = gmax(error);
\end{verbatim}\end{quotation}

assigns the maximum of all the local values of {\tt error} to 
each local copy of {\tt maxerror}.
\dino\ also provides two reduction functions,
``gmaxdex''\indexB{reductions}{gmaxdex()}\indexA{gmaxdex() reduction function}
and ``gmindex'',\indexB{reductions}{gmindex()}%
\indexA{gmindex() reduction function}
that take two parameters;
the first is the value to be reduced
and the second is (a pointer to) an integer index.
This is a user-defined index and is not related to any environment index;
The programmer is responsible for assigning a unique index number to each
environment participating in the reduction.
When these functions return, the second parameter returns 
(points to) the index of the maximum (or minimum) value.    

The reduction functions can be called with an explicit
``active set''\indexB{active-set}{in reduction functions}%
\indexB{reductions}{use of an explicit environment set}%
\indexB{environment expressions}{in reductions}%
\indexB{environment sets}{in reductions}
(using the optional \verb$`{' ENV_EXP `}'$) in the same
way that a composite procedure or a remote data reference can.  
The active set specifies which environments 
will participate in the reduction.
The first argument of a one argument
reduction may evaluate to a (sub)array,\indexB{arrays}{in reductions}
rather than a scalar, in which case
the reduction operation is performed individually over each component
of the (sub)array.

It is implicit in a reduction call that synchronization%
\indexB{synchronization}{in reductions}
between all participating environments
is involved, and that all participating
environments must reach the call, otherwise execution is blocked.
The environments do not necessarily have to execute identical
lines of code, but simply the same operation with matching parameter types.
Reductions are implemented using efficient, tree-based
computation and communication.  

\vbox{
\subsectionX{Subarrays and Ranges}
\label{subarrays and ranges}
\indexB{arrays}{using subarrays}

\begin{verbatim}
PRIMARY ::= PRIMARY ( `[]' | `[<' EXPRESSION `,' EXPRESSION `>]' ).
\end{verbatim}
}

To use most distributed memory multiprocessors efficiently,
it is important to send messages consisting of blocks of data,
rather than multiple messages consisting of single data elements,
whenever possible.
In order to efficiently move blocks of data between environments, \dino\ 
provides the ability to specify subarrays,
and to use arrays and subarrays in simple assignment statements,
which may include remote reads and writes 
(C provides no subarray facilities.)

A rectangular subsection
of an array is specified by giving the first and the last element for each
axis, e.g. ``{\tt A[<$i$,$j$>]}''.  
The index numbers are separated by a comma and enclosed in angle
brackets.  
The default value, specified by ``\verb|[]|'', is
all elements of the array along the indicated axis.

Arrays or subarrays, including remote references to them,
may be used in assignment statements\indexB{arrays}{in assignments}
of the form
\begin{quotation}
{\tt A[<$I_1$,$J_1$>]\ldots[<$I_n$,$J_n$>] =
B[<$K_1$,$L_1$>]\ldots[<$K_n$,$L_n$>]};
\end{quotation}
The size and shape of the operands in the statement must be consistent,
and the indices of the left and right operand are mapped
to each other in the obvious manner.  
If the left operand is a remote reference to a distributed array,
then the target 
environments of each element depend on the mapping function.  
In this way an entire array can be distributed over a set of 
environments in a single write,
with different portions possibly going to different environments.  
Conversely, if the right operand is a remote reference
to a distributed (sub)array,
this (sub)array is gathered
from one or more environments in a single read.  

\dino\ also allows the use of arrays and subarrays as parameters for 
composite procedures and reduction functions, 
and allows ranges to be used in specifying environment sets.

\subsectionX{User-Defined Mappings}
\label{user defined mappings}
\indexA{user defined mappings}
\indexB{mapping functions}{user defined}

\subsubsectionX{Mapping Philosophy}
\label{mapping philosophy}

There are two general categories of information that
programmer specified mappings in \dino\ include:
information about data distribution,
and information about communication patterns.
That is,
a mapping function may serve two purposes.  It allows the compiler to
statically map the data to the processors.  It also
allows the compiler to do a static analysis of communications
resulting in more efficient communication.
 
The obvious purpose for a mapping is to allow the compiler to
partition\indexB{partitioning of data structures}{via mapping functions}
the data among the processors.  While this may seem to
simply be a matter of dividing a data structure up into ``pieces''
and sending each ``piece'' to a processor, in \dino\ it is somewhat more
complex.  It is often useful to have the same data value
available to many processors.  Although this can be implemented by
having the programmer communicate the needed value once the data has
been partitioned, it may be more efficient and easier for the
programmer to think about the problem if the mapping allows for
replication\indexB{replication of data structures}{via mapping functions}
of the same ``piece'' on many processors.
 
Related to the concept of replicating data so that more than one
processor may make use of it is the fact that the programmer may wish
to update that value during the program.  For this purpose, \dino\ mappings
may also be used to provide some high level information about
communication patterns (using overlaps\indexA{overlaps}%
\indexB{mapping functions}{overlaps}.)
In order to have a communication, the
compiler must know ``what'' piece of data is being communicated,
``when'' is it being communicated, ``where'' is it being communicated
to (from), and ``how'' it is communicated.  \dino\ allows the programmer
to specify what data piece is to be communicated and when (lexically)
it is to sent and received.  The compiler can then determine, based on the
mapping, where it is to go to (or come from) and how the communication
will be handled (all the underlying detail of messages).
 
To do this, \dino\ uses the following paradigm: First,
when a data structure is mapped onto an environment structure,
a partition is implicitly defined.
That is, each ``piece'' of data is
assigned to one processor that ``owns'' the data.  We call
this the ``home'' processor\indexA{home environment}
for that piece of data.  Second, any
other processor that will need to use that piece of data is
assigned the same piece, but this processor is designated as a
``copy'' processor\indexA{copy environment}
for that piece of data.  Then, all sends and
receives for this piece of data are from the home processor to all its copy
processors.  With this paradigm a parallel program
is guaranteed to be deterministic,\indexA{determinism}
and communication patterns can be
described simply by specifying the copy processors, if any, for each
piece of data.  This default paradigm can be overridden by
the programmer but it is sufficient for many numerical algorithms.
 
\vbox{
\subsubsectionX{Mapping Definition}
\label{mapping definition}
\indexB{mapping functions}{defining new mapping functions}

\begin{verbatim}
MAPPING_FUNCTION ::=
    `map' IDENTIFIER `=' ( `[' MAP_TYPE [ALIGN] `]' )+.

MAP_TYPE ::= `all' | `compress' | BLOCK_MAP | WRAP_MAP.

BLOCK_MAP ::=
    `block' [ `overlap' [ EXPRESSION ]] [ `cross' `axis' EXPRESSION ].

WRAP_MAP ::= `wrap' [ EXPRESSION ].

ALIGN ::= `align' `axis' EXPRESSION.
\end{verbatim}

We have attempted to provide a general mapping mechanism that still
allows efficient implementation at compile time.  Our mapping
specification describes how to map arrays of data onto arrays of
processors and is based on describing how each axis of the data
structure is mapped to the processor structure (a sub-specification).
By having an (almost) orthogonal set of sub-specifications, a
powerful mapping specification can be constructed out of a simple set
of primitives.
}
 
A mapping specification is defined in three steps.  First, the
programmer specifies how each axis of the data structure is matched
to one or more axes of the structure of processors.  Second, the
programmer specifies how the data on that axis is distributed among
the processors defined in the first step.  There are three basic
choices for this step, complete replication, partition, or partition
with copies.  Third, if partition with copies is desired, the
programmer specifies how the copies of data are distributed to other
processors.  
 
In the first step, matching axes of the data structure to axes of the
structure of processors, there are only two primitives ---
``compress''\indexA{``compress'' keyword}%
\indexB{mapping functions}{``compress''} and
``align''.\indexA{``align'' keyword}\indexB{mapping functions}{``align''}
With compress, the programmer specifies
that this data axis will not be distributed.  This primitive is
used if the data structure has more axes than the structure
of processors.  With align, the programmer specifies
that a particular axis in the data structure should be mapped to a
particular axis in structure of processors.  If this primitive is
omitted for an axis in the data structure, the obvious default of
mapping the next available data axis to the next processor axis is used.
(A data axis might not be available because it has been designated
as ``compress''.)
 
For example, if the programmer is mapping a two dimensional matrix to
a vector of processors, a mapping specification of the form:
\addtolength{\parskip}{-5pt}
\begin{quotation}\begin{verbatim}
[ . . . ][compress]
\end{verbatim}\end{quotation}
will distribute rows to the processors and a specification of the
form:
\begin{quotation}\begin{verbatim}
[compress][ . . . ]
\end{verbatim}\end{quotation}
will distribute columns. The specific mapping of the
rows or columns will depend on what goes in the \verb$[ . . . ]$
sub-specification,
something that the programmer determines in steps two and three.
\addtolength{\parskip}{5pt}
 
If the programmer is mapping a two dimensional matrix to a two 
dimensional structure of processors, the mapping specification:
\addtolength{\parskip}{-5pt}
\begin{quotation}\begin{verbatim}
[ . . .  align 1][ . . .  align 0]
\end{verbatim}\end{quotation}
would cause the second axis of the data structure to map to the first
axis of the structure of processors, and the first axis of the data
structure to map to the second axis of the structure of processors.
In effect this allows the matrix to be transposed and placed on the
processors.
\addtolength{\parskip}{5pt}
 
In the second step, the distribution of a data axis to a processor
axis, there are three mapping primitives ---
``all'',\indexA{``all'' keyword}%
\indexB{mapping functions}{``all'' (as mapping primitive)}
``block'',\indexA{``block' keyword}%
\indexB{mapping functions}{``block''}
and ``wrap''.\indexA{``wrap'' keyword}%
\indexB{mapping functions}{``wrap''}
Using the first of these, the programmer can specify that
the data axis be completely replicated across the associated axis of
the structure of processors.  With the second or third, the
programmer can specify that the data axis is distributed in either
one of two ways --- blocked or wrapped.  Block mappings assign one
(approximately) equal sized contiguous piece of the data structure
to each processor.  Wrap mappings assign every $P$\/th position on
the data axis to the same processor (assuming $P$ processors).  Wrap
is essentially a variant on block that is used for improved load
balancing in a wide variety of parallel numerical algorithms.  The
programmer may also specify the width of the wrap.
 
If, in our first example, the matrix is $N$ by $N$ and there are $P$
processors with $N = 4P$, then a mapping specification with:
\addtolength{\parskip}{-5pt}
\begin{quotation}\begin{verbatim}
[block][compress]
\end{verbatim}\end{quotation}
would distribute four contiguous rows to each processor.   Alternatively,
\begin{quotation}\begin{verbatim}
[compress][wrap]
\end{verbatim}\end{quotation}
would put column $0$, $P$, $2P$, \ldots on processor $0$, etc.
\addtolength{\parskip}{5pt}
 
In the third step, the specification of a distribution for copies,
there are two mapping primitives that the programmer can use ---
``overlap''\indexA{``overlap'' keyword}%
\indexB{mapping functions}{``overlap''}
and ``cross''.\indexA{``cross'' keyword}%
\indexB{mapping functions}{``cross''}
``overlap'' specifies that copies of
neighboring data points on that axis will be available on each
processor.  The programmer can specify the direction and depth of the
overlap.  ``cross'' allows the programmer to specify that copies will
be available for data points that are found in the intersection of
two or more overlaps --- in effect making copies of neighboring data
points along diagonals available on each processor.  This might be
used, for example, in an algorithm that requires a nine point
stencil.
 
For example, if a vector $[\,x_0\;\;x_1\;\;x_2\;\;x_3\,]$ is
distributed across a vector of four processors with the
mapping specification
\addtolength{\parskip}{-5pt}
\begin{verbatim}
    [block overlap 1,1]
\end{verbatim}
the four processors will have the following elements:
\[
\begin{array}{lrrrrrr}
processor\;0 & \quad [\: x_0    & x_1 &   &   \ ] \\
processor\;1 & \quad [\: x_0    & x_1 & x_2 &   \ ] \\
processor\;2 & \quad [\:\:\;\;\;& x_1 & x_2 & x_3 \ ] \\
processor\;3 & \quad [\:\:\;\;\;&     & x_2 & x_3 \:] 
\end{array}
\]
The notation ``{\tt 1,1}'' specifies overlaps of one element to the
left and right respectively.
More precisely, the first ``\verb|1|'' means that each environment
will have a single element for the environment with the next lower index.
The second ``\verb|1|'' means that each environment will have a single
element from the environment with the next lower index.
Note that the ``leftmost'' and the
``rightmost'' processors will receive 1 element that is a copy
instead of two, i.e., there is no wrap around.  The home processor
of each data element is the processor it would be mapped to if the
overlap were omitted, in this case processor $i$ for $x_i$.
\addtolength{\parskip}{5pt}
 
If we distribute an $N$ by $N$ matrix across an $N$ by $N$ structure
of processors with the following mapping specification:
\addtolength{\parskip}{-5pt}
\begin {quotation}\begin{verbatim}
[block overlap 1,1 cross 1][block overlap 1, 1]
\end{verbatim}\end{quotation}
then the data on each processor (except the edge processors) will
have the following pattern (nine point stencil):
\[
\left[
\begin{array}{ccc}
c & N & c \\
W & D & E \\
c & S & c
\end{array}
\right]
\]
where $D$ is the data for that processor, $N$, $S$, $E$, and $W$ are
copies of data from four neighboring processors due to the overlap
primitive, and the $c$'s are copies of data from the four diagonal
neighbors due to the cross primitive.
\addtolength{\parskip}{5pt}
 
Using this structured approach allows us to combine a rather small
set of primitives for each data axis to generate a very large set of
mappings from data structures to processors.  For example, if an $N$
by $N$ matrix is to be distributed across a vector of $N$ processors
so that each processor received a column plus copies of the two
columns to the left of ``its'' column, the mapping would be:
\addtolength{\parskip}{-5pt}
\begin{quotation}\begin{verbatim}
[compress][block overlap 2,0]
\end{verbatim}\end{quotation}
The ``leftmost'' and the ``next leftmost'' processors will receive,
respectively, 0 and 1 columns that are copies.
\addtolength{\parskip}{5pt}
 
As a final example, if an $N$ by $N$ matrix is to be distributed
across a vector of $P$ processors, where $N$ is 16 and $P$
is 4, so that each processor receives copies of the closest row from
the two processors next to it, the mapping would be:
\addtolength{\parskip}{-5pt}
\begin{quotation}\begin{verbatim}
[block overlap 1,1][compress]
\end{verbatim}\end{quotation}
The resulting data structure on a processor (for an interior
processor) would be:
\[
\left[
\begin{array}{cccccccc}
u & u & u & u & u & u & u & u \\
D & D & D & D & D & D & D & D \\
D & D & D & D & D & D & D & D \\
D & D & D & D & D & D & D & D \\
D & D & D & D & D & D & D & D \\
d & d & d & d & d & d & d & d
\end{array}
\right]
\]
where $D$ is the home data for that processor, and $u$ and $d$
are copies of data from the processors  above and below
respectively.

\sectionX{\protect\dinoB\ Examples}
\label{examples}
\indexA{examples}

This section contains a number of \dino\ examples, which illustrate most
of the features of \dino.
Each example is listed on its own page, with the path
name of the file, relative to the examples directory,
at the top of the page.
An \underline{Index of Features} is provided
which allows you to find an example program containing the feature you
want to look at.
The Index lists only one example for each feature, even though some features
may be illustrated in many examples.

\subsectionX{Index of Features}
\indexB{examples}{index of features}

\begin{entry}{Environment structures}
	\entryX{Scalar (the host)\leaderfill helloworld/ex1.d}
	\entryX{One dimensional\leaderfill helloworld/ex1.d}
	\entryX{Two dimensional\leaderfill helloworld/ex2.d}
	\entryX{One environment other than the host\leaderfill
		helloworld/ex1.d}
	\entryX{Multiple environments other than the host\leaderfill
		helloworld/ex4.d}
	\entryX{Environment id's\leaderfill helloworld/ex1.d}
\end{entry}
\begin{entry}{Composite procedures}
	\begin{entry}{Declarations}
		\entryX{One composite procedure per
			environment\leaderfill helloworld/ex1.d}
		\entryX{Multiple composite procedures per
			environment\leaderfill helloworld/ex3.d}
		\begin{entry}{Formal parameters}
			\entryX{In\leaderfill matvec/ex1.d}
			\entryX{Out\leaderfill matvec/ex1.d}
			\entryX{In/Out\leaderfill smoothing/ex1.d}
			\entryX{Distributed
				parameters\leaderfill matvec/*}
			\entryX{Non-distributed
				parameters\leaderfill smoothing/ex1.d}
		\end{entry}
	\end{entry}
	\begin{entry}{Calls}
		\entryX{Implicit call
			(to all environments)\leaderfill helloworld/ex1.d}
		\entryX{Explicit call
			(using environment expressions)\leaderfill \boxY{not illustrated}}
		\begin{entry}{Actual parameters}
			\entryX{Complete\leaderfill matvec/ex1.d}
			\entryX{Ranges\leaderfill \boxY{not illustrated}}
		\end{entry}
	\end{entry}
\end{entry}
\begin{entry}{Distributed data}
	\begin{entry}{Mapping functions}
		\begin{entry}{Shape}
			\entryX{1D onto 1D\leaderfill matvec/ex1.d}
			\entryX{2D onto 1D\leaderfill matvec/ex1.d}
			\entryX{2D onto 2D\leaderfill matvec/ex7.d}
		\end{entry}
		\entryX{Axis alignment\leaderfill \boxY{not illustrated}}
		\begin{entry}{All mapping (global)}
			\entryX{As input\leaderfill matvec/ex1.d}
			\entryX{As output\leaderfill \boxY{not illustrated}}
		\end{entry}
		\begin{entry}{Individual axis mappings}
			\begin{entry}{Block mapping}
				\entryX{One element per
					environment\leaderfill matvec/ex1.d}
				\entryX{Multiple, even \#'s of elements per
					environment\leaderfill matvec/ex2.d}
				\entryX{Uneven \#'s of elements per
					environment\leaderfill matvec/ex3.d}
				\entryX{Overlaps\leaderfill smoothing/*}
			\end{entry}
			\begin{entry}{Wrap mapping}
				\entryX{Uneven \#'s of elements per
					environment\leaderfill complex/lu.d}
				\entryX{Wraps of size greater than
				        1\leaderfill \boxY{not illustrated}}
			\end{entry}
			\entryX{All mapping (single axis)\leaderfill
				matvec/ex7.d}
		\end{entry}
		\entryX{Cross mappings\leaderfill smoothing/ex5.d}
		\begin{entry}{Pre-defined mapping functions}
			\entryX{Block\leaderfill matvec/ex1.d}
			\entryX{BlockOverlap\leaderfill \boxY{not illustrated}}
			\entryX{Wrap\leaderfill \boxY{not illustrated}}
			\entryX{BlockRow\leaderfill matvec/ex1.d}
			\entryX{BlockRowOverlap\leaderfill
				smoothing/ex1.d}
			\entryX{WrapRow\leaderfill \boxY{not illustrated}}
			\entryX{BlockCol\leaderfill matvec/ex5.d}
			\entryX{BlockColOverlap\leaderfill
				smoothing/ex2.d}
			\entryX{WrapCol\leaderfill complex/lu.d}
			\entryX{BlockBlock\leaderfill matvec/ex7.d}
			\entryX{FivePt\leaderfill smoothing/ex3.d}
			\entryX{NinePt\leaderfill smoothing/ex5.d}
		\end{entry}
		\entryX{User-defined mapping functions\leaderfill matvec/ex5.d, smoothing/ex6.d}
	\end{entry}
	\begin{entry}{Local reference to distributed data}
		\entryX{Array access\leaderfill complex/lu.d}
		\entryX{Scalar access\leaderfill matvec/ex1.d}
	\end{entry}
	\begin{entry}{Communications}
		\begin{entry}{Synchronous Communications}
			\entryX{Implicit case\leaderfill smoothing/ex1.d}
			\entryX{Explicit case\leaderfill complex/lu.d}
			\entryX{Scalar communications\leaderfill \boxY{not illustrated}}
				\begin{entry}{Vector communications}
				\entryX{Complete dimension\leaderfill
					smoothing/ex1.d}
				\entryX{Ranges\leaderfill smoothing/ex3.d}
			\end{entry}
		\end{entry}
		\entryX{Asynchronous Communications\leaderfill
			smoothing/ex5.d}
	\end{entry}
	\begin{entry}{Scoping}
		\entryX{Distributed data declared as a parameter\leaderfill
			matvec/ex1.d}
		\entryX{Distributed data declared inside a composite
			procedure\leaderfill complex/lu.d}
		\entryX{Distributed data declared inside an environment
			structure\leaderfill complex/block.d}
		\entryX{Distributed data shared between two or more environment
			structures\leaderfill \boxY{not illustrated}}
	\end{entry}
\end{entry}
\begin{entry}{Reductions}
	\begin{entry}{Functions}
		\entryX{gsum() \{one parameter variety\}\leaderfill
			matvec/ex5.d}
		\entryX{gmaxdex() \{two parameter variety\}\leaderfill
			???}
	\end{entry}
	\begin{entry}{Set to reduce over}
		\entryX{Complete environment\leaderfill matvec/ex5.d}
		\entryX{Explicit subset (using environment
			expressions)\leaderfill matvec/ex7.d}
	\end{entry}
	\begin{entry}{Data to reduce over}
		\entryX{Scalar\leaderfill \boxY{not illustrated}}
		\entryX{Vector\leaderfill matvec/ex5.d}
	\end{entry}
\end{entry}
\begin{entry}{Miscellaneous features}
	\entryX{:: operator\leaderfill helloworld/ex5.d}
\end{entry}
\begin{entry}{Environment expressions}
	\begin{entry}{Construction of envexp's}
		\entryX{Ranges\leaderfill matvec/ex7.d}
		\entryX{+ operator\leaderfill \boxY{not illustrated}}
		\entryX{-- operator\leaderfill complex/lu.d}
	\end{entry}
	\entryX{In composite procedure calls\leaderfill \boxY{not illustrated}}
	\entryX{In reductions\leaderfill matvec/ex7.d}
	\entryX{In explicit communications\leaderfill complex/lu.d}
	\begin{entry}{Environment variables}
		\entryX{Declaration\leaderfill \boxY{not illustrated}}
		\entryX{Assignment\leaderfill \boxY{not illustrated}}
		\entryX{From construct\leaderfill \boxY{not illustrated}}
		\entryX{Caller variable\leaderfill \boxY{not illustrated}}
	\end{entry}
	\entryX{Comparison of environment expressions\leaderfill \boxY{not illustrated}}
\end{entry}
\begin{entry}{Linking to external functions}
	\entryX{Include directives\leaderfill complex/block.d}
	\entryX{Calling external C files\leaderfill matvec/ex4.d}
	\entryX{Using dino.h\leaderfill matvec/ex1.d}
\end{entry}
\begin{entry}{Ranges}
	\entryX{In array reads and writes\leaderfill complex/lu.d}
	\entryX{In environment expressions\leaderfill matvec/ex7.d}
	\entryX{In communications\leaderfill smoothing/ex1.d}
\end{entry}

\newpage
\subsectionX{``Hello World''}
\indexB{examples}{``Hello World'' programs}

The programs in this section simply print out messages from the environments
created in the programs.  They illustrate how to declare environment
structures and simple composite procedures.

\doex{1.1}{examples/helloworld/ex1.d}
\doex{1.2}{examples/helloworld/ex2.d}
\doex{1.3}{examples/helloworld/ex3.d}
\doex{1.4}{examples/helloworld/ex4.d}
\doex{1.5}{examples/helloworld/ex5.d}

\subsectionX{Matrix-Vector Multiply}
\indexB{examples}{matrix vector multiply examples}

These programs all solve the identical problem --- a matrix-vector
multiplication, but each program divides the data up among the processors in
different ways.

\doex{2.1}{examples/matvec/ex1.d}
\doex{2.2}{examples/matvec/ex2.d}
\doex{2.3}{examples/matvec/ex3.d}
\doex{2.4}{examples/matvec/ex4.d}
\doex{}{examples/inc/map.c}
\doex{2.5}{examples/matvec/ex5.d}
\doex{2.6}{examples/matvec/ex6.d}
\doex{2.7}{examples/matvec/ex7.d}

\subsectionX{Smoothing Algorithms}
\label{smoothing algorithms}
\indexB{examples}{smoothing algorithms}

The programs in this section perform a "smoothing" algorithm.  Each point
is continually recomputed to be the average of some subset of the points
around it.  These examples demonstrate the use of overlaps in mapping
functions.

\doex{3.1}{examples/smoothing/ex1.d}
\doex{3.2}{examples/smoothing/ex2.d}
\doex{3.3}{examples/smoothing/ex3.d}
\doex{3.4}{examples/smoothing/ex4.d}
\doex{3.5}{examples/smoothing/ex5.d}
\doex{3.6}{examples/smoothing/ex6.d}

\subsectionX{Complex Examples}
\indexB{examples}{complex examples}

These final examples were included to show how somewhat more complex \dino\
programs are put together.  They illustrate a number of features not found
in the earlier examples.

\doex{4.1}{examples/complex/mm.d}
\doex{4.2}{examples/complex/redblack.d}
\doex{4.3}{examples/complex/row.d}
\doex{4.4}{examples/complex/lu.d}
\doex{4.5}{examples/complex/block.d}
\doex{}{examples/complex/input.dat (data file for block.d)}

\sectionX{How to use \protect\dinoB}
\label{using dino}
\indexA{using DINO}

\subsectionX{Overview}

The \dino\ compiler takes a program file written in the \dino\ language,
and converts it into one or more C programs, one for each environment
structure in the \dino\ program.  In addition, \dino\ is normally set up
to move these C files to the appropriate parallel machine and compile
them into executables which can be run on that machine.
The \dino\ compiler will run on a sun3 or a sun4.
The following sections describe how to invoke the compiler,
how to control the default options by using environment variables,
and how to manually control the copying and subsequent compilation of
the intermediate C files.

\subsectionX{Setting up}
\indexB{DINO}{setup}

In order to use \dino, you must have the correct path to the \dino\ compiler.
\dino\ uses the sun convention that binaries are kept in
architecture-specific directories such as: \verb|~dino/bin/sun3| or
\verb|~dino/bin/sun4|.

For this to work correctly, you must have set the environment variable
``{\shrink \tt ARCHTYPE}'' to the appropriate architecture.
This can be done using the command

\begin{quoteX}\noindent
\verb|setenv ARCHTYPE `arch`|
\end{quoteX}

\noindent
Once this is done, the necessary \dino\ directory can be added to your path
with the command

\begin{quoteX}\noindent
\verb|set path=($path| \path\verb|/bin/${ARCHTYPE})|
\end{quoteX}

\noindent
where \path\ is the full path name to the master \dino\ directory
(if you don't know where that is, see your system administrator).

These commands should be placed in your .cshrc or .login file, after the
path is set up.  If this is not done correctly, \dino\ will fail in
mysterious ways.

In addition, a similar ``{\shrink \tt ARCHTYPE}'' variable must be set up on
the parallel machine which you're going to use.
This is used so that the \dino\ compiler knows what libraries to link with
on the target machine.
It also controls options passed to the C compiler.
A command such as

\begin{quoteX}\noindent
\verb|setenv ARCHTYPE| \boxY{machtype}
\end{quoteX}

\noindent
should be inserted in your .cshrc file
(\underline{not} the .login file -- because the .login file isn't looked
at when rsh is used)
on the target machine, where
\boxY{machtype}\ is either {\tt iPSC1}, {\tt iPSC2}, or {\tt i860}
as appropriate.

Finally, if you want to use the facility for copying the intermediate C
files to the target machine and compiling them there, you need to have
appropriate permissions set up on the parallel machine to allow for this.
Normally, this means having appropriate entries in your ``.rhosts'' file
on the parallel machine.  Consult your system administrator for assistance.

\subsectionX{Invoking the Compiler}
\indexB{DINO}{Invoking the compiler}
\label{compiler options}

The dino compiler is invoked by using the following command:

\begin{quotation}\noindent
\verb|dino [-|\boxY{machine}
    \verb|] [-w] [-c] [-n] [-e] [-l] [-o] [-p]|\\
\qquad\verb|[-D] [-P] [-Q] [-h[elp]] [-s |\boxY{suffix}\verb|] [-C |
    \boxY{num}\verb|]|\\
\qquad\verb|[-d |\boxY{directory}\verb|] [-u |\boxY{user}\verb| [-I |\boxY{directory}\verb|]|\boxY{file}
\end{quotation}

\noindent
If \verb|dino| is typed alone (or with the -D or -h options),
then a list of options is printed out.
Otherwise, \dino\ compiles the given file (which must have the \verb|.d|
extension)
into one or more C files, and may optionally send these C files to the parallel
machine, and compile them.
Options to the compiler which are boolean (for example, -w) may be turned off
by inserting a ``\verb|^|''; for example, the option ``-\verb|^|w'' turns on warning messages.
Compiler options may be listed an any order, and are described below:

\begin{itemize}

\itemY{-\boxY{machine}}
Generates code for the given parallel machine.  This option sets up all of
the default options for the given machine.  The appropriate \boxY{machine}
to use should be given to you by the system administrator.
For example, if you want to compile a program {\tt prog.d}
for a machine named {\tt mach}, the appropriate command would be

\begin{quotation}\noindent
\verb|dino -mach prog.d|
\end{quotation}

\itemY{-D}
This option causes \dino\ to list each of the parallel machines
defined, along with the options specified by them.  Any of these options
can be overridden by a command line option.

\itemY{-w}
Suppresses the printing of warning messages from the \dino\ compiler.

\itemY{-c}
Causes \dino\ to print out comments from the compiler.
There are no useful comments produced by the \dino\ compiler at this time.
This option is present for future versions of the compiler.

\itemY{-n}
Causes the \dino\ compiler to print out notes from the compiler.
There are no useful notes produced by the \dino\ compiler at this time.
This option is present for future versions of the compiler.

\itemY{-e}
Causes the \dino\ compiler to print out errors in the order in which the
compiler detects them, rather than in lexical order.  This is useful because
the compiler will occasionally report a cascaded error before the actual
error.

\itemY{-o}
Causes the compiler to use the old suffix model, producing files of the form
{\tt \boxY{env}\boxY{suffix}.c}, where the default \boxY{suffix} is
{\tt D1}, {\tt D2}, {\tt D8}, {\tt S1}, {\tt S2}, or {\tt G},
depending on the kind of machine you're compiling for.
Normally, files are named {\tt \boxY{program}.\boxY{suffix}.\boxY{env}.c},
where \boxY{program} is the name of the \dino\ program being compiled
(without the {\tt .d} suffix),
\boxY{env} is the name of the environment,
and the default \boxY{suffix} is the name of the
machine being compiled for.  The \boxY{suffix} can be changed by using the
\verb|-s| option.

\itemY{-s \boxY{suffix}}
Sets the \boxY{suffix} used to construct filenames for the intermediate C files.
See the -o option.

\itemY{-P}
This option causes \dino\ to stop just after generating the intermediate C
files, without copying them to the parallel machine.

\itemY{-p}
This option causes \dino\ to generate the intermediate C files, and copy them
to the parallel machine, but not compile them.  This option is useful when
custom flags must be sent to the C compiler on the parallel machine.

\itemY{-Q}
Prevents \dino\ from producing any output, except from error messages.
Notice that this option has no effect on the C compiler invoked by
\dino\, so if the C compiler prints out any messages (like the C
compiler on the iPSC1), they will still be printed out.

\itemY{-h[elp]}
Prints out a list of available options, with brief descriptions.
This action is also taken is no filename is given.

\itemY{-C \boxY{num}}
Sets the dimension of the cube being compiled for.  It is up to you to
insure that this many nodes are actually provided when the program is run.

\itemY{-d \boxY{directory}}
Tells \dino\ where to put your executable files.  This option accepts either
relative or absolute pathnames.
The system administrator has defined a default ``base'' directory when
\dino\ was set up.  The relative path names are always with respect to
this ``base'' directory.  In a typical installation, the ``base'' directory
would be the directory you are in if the parallel machine is a local machine,
and your home directory on the parallel machine if the parallel machine is
a remote machine.
The ``\verb|-d|'' option interprets a ``\verb|.|'' which is the first character
in a pathname as the current directory (this only works if the file system
you're using is cross mounted).
So, if you want your final files to appear in a subdirectory (of your
current directory) named ``test'', you would use the command

\begin{quoteX}\noindent
\verb|dino -mach -d ./test row.d|
\end{quoteX}

\noindent
where ``mach'' is a parallel machine which mounts your files.
If the directory does not exist, \dino\ will create it automatically.

\itemY{-u \boxY{user}}
Use the ``\verb|-u|'' option
if you want to execute commands on a remote parallel
machine as someone other than the default user (usually, the default user
will be the same as the user of the local machine).
Note that the \boxY{user} must have a login on the parallel machine.
Typing ``\verb|-u ~|'' sets the user on the parallel machine to the the same as the
current user on the local machine.  If the parallel machine is the same as
the local machine (for example, a simulator or a distributed sun network)
then ``\verb|~|'' is the only user that the ``\verb|-u|'' option will accept.

\itemY{-I \boxY{directory}}
This option tells \dino\ what directory to find include files in.
More than one ``-I'' option may be used.

\end{itemize}

\subsectionX{Using Environment Variables}
\label {environment vars}

Anything (except the name of the \dino\ source file) which can be set from the
command line can also be specified as an environment variable.
This gives the user considerable control over the default settings of the
\dino\ compiler.  In addition, many of the defaults can be set differently
for different parallel machines (assuming that your \dino\ compiler has
been configured form more than one parallel machine).

In the following descriptions, \boxY{name} stands form the name of a particular
parallel machine.  For example, if you have an iPSC2 named ``mach'',
then D\boxY{name}size for mach would be ``Dmachsize''.
Obviously, the use of \boxY{name} in an environment variable indicates that
a separate default can be set for each parallel machine.
The various environment variables are:

\begin{itemize}

\itemZ{Dmachine}
The default parallel machine that will be used if no machine is specified
on the command line.

\itemZ{Dinc}
List of directories which \dino\ will look in for include files.
Corresponds to the ``{\tt -I}'' command line option.
Multiple directories are separated by spaces, tabs, or newlines.

\itemZ{D\boxY{name}size}
The default cube size for the parallel machine \boxY{name}.
Corresponds to the ``{\tt -C}'' command line option.

\itemZ{D\boxY{name}suf}
The default suffix for the parallel machine \boxY{name}.
Corresponds to the ``{\tt -s}'' command line option.

\itemZ{D\boxY{name}dir}
The default directory on the parallel machine \boxY{name}.
Corresponds to the ``{\tt -d}'' command line option.

\itemZ{D\boxY{name}usr}
The default user on the parallel machine \boxY{name}.
Corresponds to the ``{\tt -u}'' command line option.

\itemZ{D\boxY{name}opt}
A list of one or more boolean options for the parallel machine \boxY{name}.
The ``\verb|-|'' characters from the command line are omitted, but
``\verb|^|'' may be used to negate an option.
For example, the string ``\verb|o^nQ|'' causes the compiler to use the
old suffix model, not print notes, and produces quiet output. 

\end{itemize}

\subsectionX {Doing Things Manually}

\dino\ depends on the {\shrink UNIX} commands ``rcp'' and ``rsh'' to
copy intermediate C files to the remote parallel machine and to compile
them there.
If these commands don't work on your system, then you will have to do
some or all of this manually.
In addition, \dino\ does not allow you to specify options to the C
compiler on the parallel machine other than the default options used by \dino.
If you want more control over the C compilation, you will have to do this
step manually.

You can stop \dino\ after the intermediate C files are created
(the ``-P'' option), or after the intermediate C files are copied to the
parallel machine (the ``-p'' option);
see Section~\ref{compiler options}.

You can have \dino\ compiler the intermediate C files on the parallel
machine with the command

\begin{quoteX}\noindent
\verb|dino2| \boxY{filenames}
\end{quoteX}

\noindent
where \boxY{filenames} is a list of all the intermediate C files.
\dino\ will expect those filenames to follow the default conventions for
\dino\ suffixes.
The ``{\tt dino -p}'' command puts files with the appropriate names on
the parallel machine.
The ``{\tt dino -P}'' command creates files with the correct names in
the current local directory, with the exception of files for the iPSC1
and iPSC2 when the new suffix model is used.  In that case,
the file name in the current directory might be
``row.mach.node.c'', but \dino\ expects to see ``node.c'' on the parallel
machine (Intel's machines do not support filenames longer than 14 characters).

Of course, you can write your own Makefile to control compilation on the
parallel machine.

\sectionX{\protect\dinoB\ Hints}
\label{hints}

\subsectionX{Known Compiler Bugs}
\indexA{bugs (in the DINO compiler)}
\indexB{DINO}{known bugs}

The following is a list of known compiler bugs.  These will hopefully
be fixed in a future version of \dino.

\begin{enumerate}

\item
You cannot do a send to an explicitly specified destination
where the value is a constant; the C programs generated by the \dino\
compiler will not compile.  Example:
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
int distributed A[10] map Block;

a[5]# {node[1]} = 1;
\end{verbatim}\end{quotation}

\noindent
will not work.

\item
Scalar environment declarations (other than the host) do not work now.
Examples:
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
environment single { . . . }
environment one[1] { . . . }
\end{verbatim}\end{quotation}

\noindent
won't work properly.

\item
Reduction functions where the reduction is done over only one environment
do not work properly.  For example:
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
A = gsum(B)# {node[id]};
\end{verbatim}\end{quotation}

will not work.

\item
Statements that mix range assignments with multiple assignments
do not work properly.  The statement
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
A[<5,12>]# {node[1]} = A[<5,12>] = B[];
\end{verbatim}\end{quotation}

will not run correctly.  If you use a range assignment, put only one
assignment in a statement.

\item
It turns out that there are some unforeseen limitations on the way you can
specify ranges in send/receive pairs.  While most pattern combinations
work, you cannot specify one half of a pair as a single and the other half
as a partial range.  That is, the send/receive pair
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
A[b][]# = . . .
. . . = A[<c,d>][]#;
\end{verbatim}\end{quotation}

will not work properly.  However,
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
A[][]# = . . .
. . . = A[<c,d>][]#;
\end{verbatim}\end{quotation}

or
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
A[b][]# = . . .
. . . = A[][]#;
\end{verbatim}\end{quotation}

will work.

\item
Three dimensional (or higher) environment structures do not work properly.

\item
If you are constructing your own mapping functions, the primitive operation
``align'' doesn't work properly in the case of a 1 x $N$ or $N$ x 1 data
structure (there are some special cases where this kind of data structure
is useful.)  Rather than using ``align'', transpose the data structure.

\item
\dino\ is quite good at only sending or receiving the proper data elements
(in the completely implicit case) even if you overspecify the data to be
sent or received.  However, there is one obvious case that will not be
handled properly.  If you have a data structure which is partitioned
(i.e., not distributed "all"), and you send it with
``\verb|A[][]# = . . .|'' or receive it with
``\verb|. . . = A[][]|'', it will not work properly.

\item
We have had some trouble with complex expressions on some machines.
\dino\ translates sends and receives into more complex expressions.
Sometimes the C compilers on target machines can't cope with them.
For example:
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
A[idx][idy]# = ((right?A[idx][0]:A[idx][idy-1]#) +
                (left?A[idx][N-1]:A[idx][idy+1]#) +
                (top?A[0][idy]:A[idx-1][idy]#) +
                (bottom?A[N-1][idy]:A[idx+1][idy]#) / 4);
\end{verbatim}\end{quotation}

translates into a C expression that won't compile on our iPSC1 and causes
the C compiler on our sun3 (when we are using the iPSC1 simulator) to
make an error in the expression evaluation.  Beware of anything approaching
this complexity.

\item
Certain sends and receives do not work properly.  They are those
sends and receive in which

	\begin{itemize}

	\item[1)] you explicitly specify the source or destination environment,
	\item[2)] the data object (with any message header generated by the
	compiler) is greater than the \dino's message buffer size
	(16K on the iPSC1, 32K on the other cubes), and
	\item[3)] the compiler thinks that storage for the whole piece of
	data (of the correct type) doesn't exist on the node.

	\end{itemize}

\noindent
So, for example, if $A[100][100]$ is a float and $B[100][100]$
is a double distributed which is not mapped entirely to your node,
the statement
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
B[][]# {node[0]} = A[][];
\end{verbatim}\end{quotation}

will not send out the whole piece of data (it only sends the first message
buffer).
The place where this gets tricky is that if $B[100][100]$ is a double
distributed that is mapped to your node, then if you write
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
B[][]# {node[0]};
\end{verbatim}\end{quotation}

the compiler won't figure out that storage exists on your node and thus doesn't
do the receive properly.  However,
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
B[][] = B[][]# {node[0]};
\end{verbatim}\end{quotation}

will work properly.

\item
If you use a range as a parameter to an ordinary C function, the \dino\
compiler will not catch it.  Instead, it generates C code with no parameter
in that position.  If there is more than one parameter to that function,
the code will be syntactically incorrect and the resulting C compilation will
fail.

\item
\dino\ allows you to specify a range in a larger data array as the actual
parameter so long as the dimension and size(s) of the range is the same as
the dimension and size(s) of the formal parameter.  However, if the
dimension of the larger data structure is higher than the dimension of the
formal parameter, this will not work properly in most cases.

For example, the composite procedure call
\verb|comp (A[<3,6>][2])#| will not work if
the formal parameter is declared to be a one dimensional vector of length 4.
If the formal parameter is two dimensional (4 x 1), it will work properly.

\end{enumerate}

\subsectionX{What the Compiler Doesn't Do (run-time checking)}
\label{run-time checking}
\indexA{run-time checking}
\indexA{run-time errors}

In general, the \dino\ compiler and run-time library do very little in the
way of run-time checking.
The only errors which are checked for at run-time are the following:

\begin{itemizeX}

\itemX {\bold{Implicit send called for data that has no copies}}

This message indicates that the \dino\ program tried to send data which
had no copies on other environments.  Usually, this occurs either because
the wrong mapping function was chosen, or because the wrong piece of the data
structure is being sent (incorrect ranges are a common cause).
The program continues running after this warning
message.

\itemX {\bold{Implicit receive called for data that is only home data}}

This message indicates that a receive has been done on data which is home
data, and thus has no home to receive from.  This usually occurs either because
the wrong mapping function was chosen, or because the wrong piece of the
data structure is being sent (incorrect ranges are a common cause).
The program continues after this warning. 

\end{itemizeX}

\noindent
These are the only errors which are caught by \dino.
The following errors, while not caught by the \dino\ run-time system,
should be watched for carefully:

\begin{enumerate}

\item
Ranges in which the left number is larger than the right.
An example of this is \verb|A[<4,3>]#|.
These errors can creep in when writing programs designed to work on arbitrary
sized data structures;  if the size of arrays becomes smaller than the number
of processors, these ``backwards ranges'' can occur.

\item
Mismatched sends and receives cannot be caught by \dino.
If your program seems to infinite loop, chances are that your sends and
receives are not matching up properly.

\item
\dino\ does no range checking.  That is, references to distributed arrays that
are less that zero or greater than the size of the array will not be flagged
in \dino.

\item
\dino\ does not check that a local reference to a distributed data structure
is actually mapped to that particular environment.

\item
\dino\ does not check those parts of range assignments that can only be
known at run time.  Thus, you can assign ranges that are not the same sizes
(with, of course, unpredictable results.)

\end{enumerate}

\subsectionX{Performance Hints}
\label{performance hints}
\indexA{performance hints}
\indexA{efficiency}

The following is a list of suggestions on how to achieve the best performance
from \dino.
The list has been kept short, and only discusses \dino-specific issues.

\begin{enumerate}

\item
Use of environment structures\indexB{structures of environments}{efficiency of}
which have more environments in them than
your cube has processors are implemented by running multiple processes
on each node of the cube.  As a result, performance is significantly
impaired.  If the \underline{total} number of environments (in all
environment structures) is less than or equal to the number of nodes,
then they are distributed so that each node gets at most one environment.

\item
When performing remote
references,\indexC{distributed data}{remote reference}{efficiency of}
it is more efficient to do block communications
than to send\indexB{sends}{efficiency of}
and receive\indexB{receives}{efficiency of} individual values,
as \dino\ sends one or more
messages for each communications statement.

\item
In addition, it is somewhat more efficient to include sends or receives
to multiple environments in a single statement, where \dino allows this.
This can occur in implicit communications, when a data structure has
multiple overlaps, and in explicit communications.

\item
Since composite procedure calls\indexB{composite procedures}{efficiency of}
must distribute their parameters
(and retrieve results), minimize the use of parameters.  Data which should
remain in the same environment structure over multiple composite
procedure calls should be declared as a variable within that environment.

\item
When referencing a distributed array, \dino\ allows the user to refer to the
global name of an object, even when only a piece of that object is present
in the environment referring to the
object.\indexB{mapping functions}{efficiency of}
As a result, \dino\ must
translate the global indices provided by the program into local indices.
This process can be somewhat time-consuming, particularly for
\bold{wrap} mappings.\indexB{``wrap'' keyword}{efficiency of}
C compilers with sophisticated optimization routines will remove many of these
computations from within loops, but we haven't seen any C compilers
that do this for the supported machines.

\item
When doing sends\indexB{sends}{efficiency of}
and receives\indexB{receives}{efficiency of}%
\indexB{remote reference}{efficiency of},
it is faster if the data to be sent (or received) from each environment
resides in a contiguous piece of memory.  In some cases, interchanging the
axes of a data structure (in order to make the communicated pieces contiguous)
can have dramatic effects on execution time.

\end{enumerate}

\sectionX{Installation Notes}
\indexA{installation}
\label{installation}

If your copy of \dino\ has not already been installed, this section of the
manual should show you how to accomplish that.  If you have problems, feel
free to contact us at \verb|dino@cs.colorado.edu|.

The \dino\ compiler is divided into two parts:  A front end, which runs on a
Sun workstation, and a back end, which runs on the parallel machine (this
could be the same machine in the case of a simulator or sun network).

\subsectionX{Installing the Front End}

This section describes how to install the front end of \dino\, and how to
configure it for your parallel machine(s).

\subsubsectionX{Where to Install \protect\dinoB}

\dino\ is designed to be installed with its own user name (dino) in it's
own directory.  It is possible to do it in other ways, but some of the
procedures in this manual will be incorrect for other kinds of installations.
If you need to do a non-standard installation, contact us for more information.

Once you have the ``dino'' username set up, change to dino's home directory.
You should either have a tape with \dino\ on it, or a compressed, tar'd
file you obtained via FTP.
If you have a tape, untar it in \dino's home directory.  If you have a file,
move it to \dino's home directory, uncompress it, and then untar it.

\subsubsectionX{Reading the README file}

Before continuing with the installation, be sure to read the
{\shrink README} file
in order to check for changes to this installation procedure.

\subsubsectionX{Setting up the \protect\dinoB\ System Files}
\label{system files}

\dino\ assumes that the shell is csh.  If you have to use sh, some of the
procedures here won't work exactly as written.

\dino\ uses the convention that binary files are kept in architecture
specific directories, such as ~dino/bin/sun3.  In order to make this
work, \dino\ must know what kind of machine it's running on, both on the
Sun workstation, and the parallel machine being used.  On the Sun, insert
the command
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
setenv ARCHTYPE `arch`
\end{verbatim}\end{quotation}

\noindent
into your .cshrc file.  On the parallel machine, a commands such as
\vspace{-18pt}
\begin{quotation}\noindent\begin{verbatim}
setenv ARCHTYPE iPSC1
\end{verbatim}\end{quotation}

\noindent
must be inserted in the .cshrc file.  The other architectures  would use
``\verb|iPSC2|'' and ``\verb|i860|''.

Notice that if your file system is cross mounted, then the .cshrc file must
determine if it's logged onto the parallel machine or a sun workstation,
and set ARCHTYPE appropriately.

Once ARCHTYPE is set up, the \dino\ path is added with:

\begin{quotation}\noindent
\verb|set path=($path |\boxY{DINO}\verb|/bin/${ARCHTYPE})|
\end{quotation}

\noindent
where \boxY{DINO} is the full path name to the master \dino\ directory.
This must be done in your .cshrc file, because commands run via ``rsh''
don't look at the .login file.

Several example .cshrc files are provided in the \verb|~dino/setup|
directory - cshrc.sun, cshrc.ipsc, and cshrc.both (used for crossmounted
home directories).

If your site has a Pascal compiler, make sure it is in the path.
Also, the .rhosts file on the parallel machine must be set up so
that \dino\ can run ``rcp'' and ``rsh'' on the sun to copy files to the
parallel machine and run commands there.

Finally, create a .forward file in the dino home directory which contains
the line ``dino@cs.colorado.edu''.
This will allow users to send mail to ``dino''
on their Suns, and it will be forwarded to us.

\subsubsectionX{How to Generate the Front End}

Once you have modified your .cshrc file, log out and log in as dino.
Then simply type:

\begin{quotation}\noindent
\verb|make compiler|
\end{quotation}

\noindent
This should install the front end of the \dino\ compiler.
If you have both Sun3 and Sun4 workstations, you will have to do this
once for each kind of workstation.

\subsubsectionX{Configuring the Front End}

\dino\ is actually a Bourne shell script, ``dino'', which calls a number
of executable programs, including the actual compiler.
In order to allow \dino\ to work with a large number of parallel machines,
\dino\ reads the configuration file ``dino.init'' every time it starts up.
This section describes how to construct this file.

We have provided an example configuration file, ``dino.init.example''.
Copy this file into ``dino.init'', and edit it.  Then make the following
changes.

\begin{itemize}

\item[\hbox{}\qquad1)] Set the environment variable \verb|Dhome| to the
home directory for dino.

\item[\hbox{}\qquad2)] Set the environment variable \verb|Dinc| to the
appropriate list of include directories.  Multiple directories
should be separated by spaces, tabs, or newlines.

\item[\hbox{}\qquad3)] Define each parallel machine you wish to support.
Notice that multiple ``virtual'' machines can be defined for each
real machine.
For each virtual machine, five words are added to the \verb|Dmachs| variable.
The exact details on how to do this are in comments in the ``dino.init''
file.
In addition, the specialized variables \verb|sD|\boxY{name}\verb|suf| and
\verb|sD|\boxY{name}\verb|opt|
can be used to specify additional defaults for the virtual machine being
defined.
Setting \verb|sD|\boxY{name}\verb|suf| allows you to set the default
suffix for the parallel machine \boxY{name} (see the ``\verb|-s|'' command
option in Section~\ref{compiler options}).
Setting \verb|sD|\boxY{name}\verb|opt| allows you to set one or more
of the boolean options for the parallel machine.
The format is the same as for \verb|D|\boxY{name}\verb|opt|
(see Section~\ref{environment vars}).

\item[\hbox{}\qquad4)] Define the \verb|sDmachine| variable to be default
virtual machine (which will be used if the \verb|dino| command line doesn't
specify a machine).

\item[\hbox{}\qquad5)] Make sure all the objects you defined are listed in
the final \verb|export| statement.

\end{itemize}

\noindent
In order to make configuration easier, the \dino\ compiler provides an option
which will print out the current configuration.
In order to do this, type the command

\begin{quotation}\noindent
\verb|dino -D|
\end{quotation}

\subsectionX{Installing the Back End}

This section describes how to install \dino's back end onto a target
parallel machine.
This process must be repeated for each parallel machine you plan to use.

\subsubsectionX{Where to Install \protect\dinoB}

As on the Suns, \dino\ is designed to be installed in its own home directory
on the parallel machine.
If your files are cross-mounted to the parallel machine(s) and the
same directory is \dino's home directory on both the Sun and
the parallel machine(s), then you are done with this part.
Otherwise,

\begin{itemize}

\item[\hbox{}\qquad1)] Create a dino account on the parallel machine.

\item[\hbox{}\qquad2)] Copy \verb|~dino/|\boxY{machine type}
from the Sun to \verb|~dino/Makefile| on the parallel machine,
where \boxY{machine type} is either \verb|iPSC1|, \verb|iPSC2|, or \verb|i860|.

\item[\hbox{}\qquad3)] Log in as ``dino'' on the parallel machine,
and type

\begin{quotation}\noindent
\verb|make directories|
\end{quotation}

\item[\hbox{}\qquad4)] Copy the contents of the directories

\begin{quoteX}\noindent
\verb|~dino/|\boxY{machine type}\verb|/Makefile|,\\
\verb|~dino/source/inc|,\\
\verb|~dino/source/library|, and\\
\verb|~dino/source/dino2|
\end{quoteX}
\noindent
to the directories of the same name on the parallel machine.

\end{itemize}

\subsubsectionX{Setting up the \protect\dinoB\ System Files}

If you followed the instructions in Section~\ref{system files},
then this is already done.

\subsubsectionX{How to Generate the Back End}

Log in on the parallel machine as ``dino'', change to the \boxY{machine type}
directory, and type

\begin{quotation}\noindent
\verb|make all|
\end{quotation}

\subsubsectionX{Configuring the Back End}

As with the front end of \dino, the back end is controlled by a Bourne
shell script (``dino2'').
This script uses two other shell scripts to determine your particular setup:
``dino2.init'' and ``dino2.\boxY{name}'', where \boxY{name} is the virtual
machine name.  Both of these files should be in ~dino/bin/local on the
parallel machine.  Example files ``dino2.init.example'' and
``dino2.\boxY{machine type}.example'' have been provided as a starting point.

To set up the ``dino2.init'' file, copy the example file to ``dino2.init''.
Then make the following changes:

\begin{itemize}

\item[\hbox{}\qquad1)] Set the environment variable \verb|Dhome| to the
home directory for dino.

\item[\hbox{}\qquad2)] Set four default parameters.
These are only used when \verb|dino2| is invoked directly from the
command line.  These variables are described in the example file
``dino2.init.example''

\end{itemize}

The ``dino2.\boxY{name}'' file contains information on options and libraries
used to compiler the intermediate C files into executables.
We have provided examples for ``plain vanilla'' cubes under the name
``dino2.\boxY{name}.example''.
Each file sets eight environment variables, which are described in the
example files.

If you find that the variables provided cannot be made to work for the way
you want to set things up, contact us.

\subsectionX {Complex Sun/Parallel Machine Interactions}

In some cases, a parallel machine is configured in a way which doesn't
``fit'' the \dino\ script model.
For example, we've encountered an iPSC2 for which ``rsh'' and ``rcp''
commands must be done from one particular Sun.
To allow for these kinds of special cases, we allow you to define a particular
parallel machine as ``special'' (see the ``dino.init'' file).
This will cause \dino\ to ignore the normal actions after the intermediate C
files are generated, and instead, attempt to execute the Bourne shell code
found in the ``dino.special'' file in \verb|~dino/bin/local|

We've provided a skeleton file ``dino.special.example'', which shows
how to have special code for more than one machine.  If you need to use
this feature, you are on your own.  If you need additional information,
feel free to contact us.

\subsectionX {Updates}

Each \dino\ installation should include a ``{\shrink \tt SPECS}'' file
in the \dino\ home
directory on the Sun.  This file describes your particular configuration,
and the date of distribution.  If you contact us with this information,
we can supply you with an update that includes only changes since your
last installation.
Alternatively, you can obtain an entirely new installation, and simply
reinstall it.

In order to install a new update of \dino, the same procedure is used as
for the initial installation, except that you should not have to reconstruct
the configuration files.

\newpage
\appendix
\sectionX{\protect\ebnfB\ Specification for \protect\dinoB\
Extensions to C}
\label{ebnf}

{
\parindent 0pt
{
\em
This \ebnf\ specification\indexA{EBFN specification}
uses the following notation:

\begin{tabbing}
xxxxxxxx \= xxxxxxxx \= \kill
\> {\tt ()} \> precedence grouping \\
\> {\tt []} \> optional \\
\> {\tt *} \> zero or more \\
\> {\tt +} \> one or more \\
\> \verb$|$ \> alternatives \\
\> {\tt ::=} \> is replaced by \\
\> \verb$||$ \> one or more separated by \\
\\
\> Terminals are enclosed in single quotes \\
\> Non-terminals are in capitals \\
\end{tabbing}
}

\underline{Program:}
\begin{verbatim}
PROGRAM ::= ( ENVIRONMENT | MAPPING_FUNCTION | DATA_DEFINITION )+.
\end{verbatim}

\underline{Environments:}
\begin{verbatim}
ENVIRONMENT ::=
    `environment' IDENTIFIER DIMENSION* `{' EXTERNAL_DEFINITION+ `}'.

DIMENSION ::= `[' EXPRESSION [ `:' IDENTIFIER ] `]'.

EXTERNAL_DEFINITION ::=
    FUNCTION_DEFINITION | DATA_DEFINITION | MAPPING_FUNCTION.
\end{verbatim}

\underline{Composite Procedure Declarations:}
\begin{verbatim}
FUNCTION_DEFINITION ::=
    `composite' IDENTIFIER `(' [COMP_PARAMETER_LIST] `)'
    FUNCTION_BODY.

COMP_PARAMETER_LIST ::= ( [`in' | `out'] IDENTIFIER ) || `,'.
\end{verbatim}

\underline{Composite Procedure Call:}
\begin{verbatim}
STATEMENT ::=
    IDENTIFIER `(' [ EXPRESSION_LIST ] `)' `#' [ `{' ENV_EXP `}' ]
    [ `::' STATEMENT ].

ENV_EXP ::= EXPRESSION.
\end{verbatim}

\underline{Distributed Data Declaration:}
\begin{verbatim}
DECLARATOR ::=
    [ `asynch' ] `distributed' DECLARATOR
    ( `[' CONSTANT_EXPRESSION `]' )+ MAPPING.

MAPPING ::= `map' ( `all' | IDENTIFIER | (( IDENTIFIER IDENTIFIER )
    || `map' )).
\end{verbatim}

\underline{Distributed Data Use:}
\begin{verbatim}
EXPRESSION ::=
    PRIMARY `#' [ `{' ENV_EXP [ `from' EXPRESSION ] `}' ].

ENV_EXP ::= `caller' | EXPRESSION.
\end{verbatim}

\underline{Subarrays and Ranges:}
\begin{verbatim}
PRIMARY ::= PRIMARY ( `[]' | `[<' EXPRESSION `,' EXPRESSION  >]' ).
\end{verbatim}

\underline{Mapping Functions:}
\begin{verbatim}
MAPPING_FUNCTION ::=
    `map' IDENTIFIER `=' ( `[' MAP_TYPE [ALIGN] EXPANSION* `]' )+.

MAP_TYPE ::= `all' | `compress' | BLOCK_MAP | WRAP_MAP.

BLOCK_MAP ::=
    `block' [ `overlap' [ EXPRESSION ]] [ `cross' `axis' EXPRESSION ].

WRAP_MAP ::= `wrap' [ EXPRESSION ].

ALIGN ::= `align' `axis' EXPRESSION.

EXPANSION ::= `expand' `axis' EXPRESSION.
\end{verbatim}

\underline{Reduction Functions:}
\begin{verbatim}
PRIMARY ::=
    REDUCTION `(' EXPRESSION [ `,' EXPRESSION ] `)' `#'
    [ `{' ENV_EXP `}' ].

REDUCTION ::=
    `gsum' | `gprod' | `gmin' | `gmindex' | `gmax' | `gmaxdex'.
\end{verbatim}
}

\vspace{0.25in}
\noindent\underline{A Note on C Syntax:}

In standard C, a \verb$PROGRAM$ consists of one or more
\verb$EXTERNAL_DEFINITION$s, each
of which can be a \verb$FUNCTION_DEFINITION$ or a \verb$DATA_DEFINITION$.
\dino\ complicates
this somewhat by adding environments.

C \verb$DATA_DEFINITION$s are built from \verb$DECLARATION_SPECIFIER$s
(e.g., int,
struct A { int B; char C}, etc.), followed by \verb$DECLARATOR$s, followed by
\verb$INITIALIZER$s.  The \verb$DECLARATOR$
is an \verb$IDENTIFIER$, optionally nested inside
one or more ``*'', ``()'', or ``[]'' to designate respectively a pointer
to, a function returning, or an array of.  \dino\ allows a single distributed
declaration in this nesting to designate a particular \verb$DATA_DEFINITION$
as distributed.

Ordinary C \verb$FUNCTION_DEFINITION$s are built by concatenating an optional
\verb$TYPE_SPECIFIER$, a
\verb$FUNCTION_DECLARATOR$ (which includes the parameter list) and a 
\verb$FUNCTION_BODY$ (which includes the parameter declarations).
\dino\ uses a
simpler syntax for composite procedures.

Certain types of C \verb$EXPRESSION$s are called \verb$PRIMARY$s
to distinguish then from
the larger class of all \verb$EXPRESSION$s.  

\closeout15

% This produces the index
\twocolumn[\begin{center}{\Large\bold{Index}}\end{center}\vspace{0.375in}]
{
\renewcommand{\idx}[2]{#2}
\catcode`\^^M=9
\parsep 0pt
\parindent -12pt
\raggedright
\input{\jobname.index2}
}

% This produces the references
\onecolumn\begin{center}{\Large\bold{References}}\end{center}\vspace{0.375in}
{
\parskip 12pt
\noindent
Rosing, M., Schnabel, R., and Weaver, R.
The DINO parallel programming language.
Department of Computer Science Technical Report CU-CS-457-90,
University of Colorado at Boulder, 1990.
To appear in {\it Journal of Parallel and Distributed Computing.}

\vspace{0.25in}

\noindent
Rosing, M., and Schnabel, R. 
An overview of DINO -- a new language for numerical computation
on distributed memory multiprocessors. In
Rodrique, G. (Ed.). 
{\it Parallel Processing for Scientific Computation.}
SIAM, 1989, pp. 312-316.

\noindent
Rosing, M., Schnabel, R., and Weaver, R. 
DINO : summary and examples.
In Fox, G. (Ed.).  
{\it The Third Conference on Hypercube Concurrent Computers
and Applications.}
ACM, 1988, pp. 472-481.

\noindent
Rosing, M., Schnabel, R., and Weaver, R. 
Expressing complex parallel algorithms in DINO.
{\it Proc. of Fourth Conference on Hypercubes, Concurrent Computers,
and Applications,}
Vol. 1 (1989), 553-560.

\noindent
Rosing, M., Schnabel, R., and Weaver, R.
Massive parallelism and process contraction in DINO.
In Dongarra, J., Messina, P., Sorensen, D.C., and Voigt, R.G. (Eds.),
{\it Parallel Processing for Scientific Computation,}
SIAM, 1990, pp. 364-369.

\noindent
Rosing, M., and Weaver, R.
Mapping data to processors in distributed memory computers.
{\it Proc. of Fifth Distributed Memory Computing Conference,}
IEEE Press, 1990, pp 884-893.
}

\end{document}
